Hi Ticker, maybe you need this? --Analyse sections that are known-- MDR 17 00000000 len=0 next=00000000 implied size=0 (0x0) MDR 18 00000000 len=0 next=00000000 implied size=0 (0x0) MDR 19 00000000 len=0 next=00000000 implied size=694 (0x2b6) MDR 16 000002b6 len=d4 next=0000038a fixed record size 212 number of records 1,00 implied size=1697585 (0x19e731) +++MISMATCH size multiplier 8007,48 8007 MDR 1 0019e9e7 len=138 next=0019eb1f fixed record size 12 number of records 26,00 implied size=312 (0x138) Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 13. Dezember 2021 15:50 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd It has the record size (even though pointless). Probably has magic/header flags but can't tell absolutely because the next mdr could start with an offset of 00 00 00 00 if empty. Ticker On Mon, 2021-12-13 at 13:51 +0000, Gerd Petermann wrote:

Hi Ticker,

not sure what you mean. Here is the output from MdrDisplay: 000000df | 3f 23 51 00 | MDR 15 at offset 0x51233f 000000e3 | d5 b3 0f 00 | MDR 15 length 1029077 |                         | End of section 0060d714, len 0x0fb3d5 000000e7 | 01 | String flag 1 |                         | 000000e8 | b6 02 00 00 | MDR 16 at offset 0x0002b6 000000ec | d4 00 00 00 | MDR 16 length 212 |                         | End of section 0000038a, len 0x0000d4 000000f0 | d4 00 | MDR 16 record size d4 |                         | Number of records 1 000000f2 | 00 00 00 00 | MDR 16 header flags 0000 |                         |

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 13. Dezember 2021 13:34 An: mkgmap-dev@lists.mkgmap.org.uk; mkgmap-svn@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.

Hi Gerd

From your example map, can you determine what settings should be used for hasRecSize and hasMagic (MdrDisplay ~line 1351 and other modules as well). I'd have expected (false, ?);

Ticker

On Mon, 2021-12-13 at 11:33 +0000, svn commit wrote:

...

Version display-r572 was committed by gerd on Mon, 13 Dec 2021

MDR16 is some kind of codebook. At least the last bytes are probably the most frequent characters in MDR 15.

http://www.mkgmap.org.uk/websvn/revision.php?repname=display&rev=572 _______________________________________________ mkgmap-svn mailing list To unsubscribe send an mail to mkgmap-svn-leave@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-svn

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

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

Hi Ticker, I looked at those offsets into MDR 15 which start a short string, means, next offset is only 2 bytes further. It seems the bits in MDR15 are read from left to right, always starting at a given offset, so the BitReader class isn't useful. I think I've identified a few codes, but don't take them for granted: 0111 -> '\0' (quite obvious since we know that the uncompressed MDR15 starts with a 0x00 and the compressed one starts with 0x70) 111 -> 'A' 1101 -> 'R' 1100 -> 'K' 01000 -> 'T' 00001010 -> '0' 00000100 -> '6' I can continue to identify more codes. A result could be a hard coded Huffman tree in MdrDisplay, which should then be able to decode all strings in Mdr15 for the given mdr file. Once that works I would try to understand how the data in MDR16 encodes the tree. Maybe you have another idea? Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 13. Dezember 2021 16:12 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd Both flags are correct - actually I should have realised this earlier as having some content makes no difference to the reading of the sequence of Mdr headers - sorry for wasting your time. Ticker On Mon, 2021-12-13 at 14:56 +0000, Gerd Petermann wrote:

Hi Ticker,

maybe you need this? --Analyse sections that are known-- MDR 17 00000000 len=0 next=00000000 implied size=0 (0x0) MDR 18 00000000 len=0 next=00000000 implied size=0 (0x0) MDR 19 00000000 len=0 next=00000000 implied size=694 (0x2b6) MDR 16 000002b6 len=d4 next=0000038a fixed record size 212 number of records 1,00 implied size=1697585 (0x19e731) +++MISMATCH size multiplier 8007,48 8007 MDR 1 0019e9e7 len=138 next=0019eb1f fixed record size 12 number of records 26,00 implied size=312 (0x138)

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 13. Dezember 2021 15:50 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.

Hi Gerd

It has the record size (even though pointless). Probably has magic/header flags but can't tell absolutely because the next mdr could start with an offset of 00 00 00 00 if empty.

Ticker

On Mon, 2021-12-13 at 13:51 +0000, Gerd Petermann wrote:

...

Hi Ticker,

not sure what you mean. Here is the output from MdrDisplay: 000000df | 3f 23 51 00 | MDR 15 at offset 0x51233f 000000e3 | d5 b3 0f 00 | MDR 15 length 1029077 |                         | End of section 0060d714, len 0x0fb3d5 000000e7 | 01 | String flag 1 |                         | 000000e8 | b6 02 00 00 | MDR 16 at offset 0x0002b6 000000ec | d4 00 00 00 | MDR 16 length 212 |                         | End of section 0000038a, len 0x0000d4 000000f0 | d4 00 | MDR 16 record size d4 |                         | Number of records 1 000000f2 | 00 00 00 00 | MDR 16 header flags 0000 |                         |

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 13. Dezember 2021 13:34 An: mkgmap-dev@lists.mkgmap.org.uk; mkgmap-svn@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.

Hi Gerd

From your example map, can you determine what settings should be used for hasRecSize and hasMagic (MdrDisplay ~line 1351 and other modules as well). I'd have expected (false, ?);

Ticker

On Mon, 2021-12-13 at 11:33 +0000, svn commit wrote:

...

Version display-r572 was committed by gerd on Mon, 13 Dec 2021

MDR16 is some kind of codebook. At least the last bytes are probably the most frequent characters in MDR 15.

http://www.mkgmap.org.uk/websvn/revision.php?repname=display&rev=572 _______________________________________________ mkgmap-svn mailing list To unsubscribe send an mail to mkgmap-svn-leave@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-svn

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

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

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

Hi Ticker, the bits in MDR15 are processed from left to right. Strings in (uncompressed) MDR15 are null terminated. So, if the MDR15 contains e.g. 07FFB8 and the offset is 1 the decode has to read 111 111 111 0111 xxx -> AAA\0 The xxx bits are ignored by the decoder, since the 0111 sequence is the null terminator. Attached is my current knowledge about the table. Just a matter of time to find the rest... Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 14. Dezember 2021 11:42 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd I was wondering if something like this could be done. Do you mean bits are read right/low to left/high, effectively reversing as it reads or is this the way the BitReader/Writer class works? Assuming bits in natural order, 0111 does look like the string terminator as it occurs at end, excluding padding, of all the strings starting at 1,11,16,20,25

From what you wrote previously: "Baca Pri Podbrdu" When I change the code to return offset 11 instead of 1 the string "Bavsica" is displayed The BA sequence should be in the leading part of 0010011110.

Assuming you get a few more chars consistently and can draw up part of a tree consistent with huffman decoding, then Mdr16 must represent this and, as latin1 chars are not obvious, they can't be byte aligned but rather placed, in-line, in the bit-stream that represents the tree. So, need to look at different ways a tree with just info in leaves can be represented and try and match it to what we see Ticker On Tue, 2021-12-14 at 09:29 +0000, Gerd Petermann wrote:

Hi Ticker,

I looked at those offsets into MDR 15 which start a short string, means, next offset is only 2 bytes further. It seems the bits in MDR15 are read from left to right, always starting at a given offset, so the BitReader class isn't useful. I think I've identified a few codes, but don't take them for granted: 0111 -> '\0' (quite obvious since we know that the uncompressed MDR15 starts with a 0x00 and the compressed one starts with 0x70) 111 -> 'A' 1101 -> 'R' 1100 -> 'K' 01000 -> 'T' 00001010 -> '0' 00000100 -> '6'

I can continue to identify more codes. A result could be a hard coded Huffman tree in MdrDisplay, which should then be able to decode all strings in Mdr15 for the given mdr file. Once that works I would try to understand how the data in MDR16 encodes the tree. Maybe you have another idea?

Gerd

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

Hi Ticker, yes, I'm close to done with the display tool being able to decode the string from Adria Topo. The 'F' is causing trouble, so probably something in my tree is still wrong or incomplete: Here's my actual code to dill the Huffman tree: add("111", 'A'); add("0111", '\0'); add("1000", ' '); add("1001", 'E'); add("1010", 'N'); add("1011", 'O'); add("1100", 'I'); add("1101", 'R'); add("01100", 'K'); add("00101", 'C'); add("00110", 'S'); add("00111", 'D'); add("01000", 'T'); add("01001", 'M'); add("01010", 'V'); add("01011", 'J'); add("01101", 'L'); add("000101", 'G'); add("000110", 'Z'); add("001000", 'P'); add("000111", 'U'); add("001001", 'B'); // add("0000000", 'F'); add("0000110", 'H'); add("0000111", '1'); add("0001001", '.'); add("00000011", '5'); add("00000100", '6'); add("00000111", '7'); add("00001000", '8'); add("00001001", '9'); add("00001010", '0'); add("00001011", '4'); add("00000101", '-'); add("000000100", '('); add("000000101", ')'); Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 14. Dezember 2021 18:09 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd Just got back to looking for some more. In addition I have: 000 (space) B 001001 D 00111 I 11001 P 001000 U 000111 V 01010 but you've probably got much further anyway Thinking of various algos to represent the tree and considering what they would make of the example Mdr16 data I haven't got anywhere. Ticker _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Ticker, yes, the tree is still incomplete. I use the existing tree and whenever it fails to decode a string I try find out the missing character looking at the original map with the search. I think you have no chance to do that without the full index file. I need a pause now and maybe tomorrow I have the complete table. Then I'll try to print it in some ways and will see if anything looks close to what I find in MDR16... Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 14. Dezember 2021 19:30 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd Do you fill in all the empty leaves with noticeable characters and report them so you can spot patterns that haven't been defined and their usage. There seem to be some chars missing still (qwxy23). I don't know if the shields/thin/fat separators make it into Mdr15 Ticker On Tue, 2021-12-14 at 17:32 +0000, Gerd Petermann wrote:

Hi Ticker,

yes, I'm close to done with the display tool being able to decode the string from Adria Topo. The 'F' is causing trouble, so probably something in my tree is still wrong or incomplete: Here's my actual code to dill the Huffman tree: add("111", 'A');

add("0111", '\0'); add("1000", ' '); add("1001", 'E'); add("1010", 'N'); add("1011", 'O'); add("1100", 'I'); add("1101", 'R');

add("01100", 'K'); add("00101", 'C'); add("00110", 'S'); add("00111", 'D'); add("01000", 'T'); add("01001", 'M'); add("01010", 'V'); add("01011", 'J'); add("01101", 'L');

add("000101", 'G'); add("000110", 'Z'); add("001000", 'P'); add("000111", 'U'); add("001001", 'B');

// add("0000000", 'F'); add("0000110", 'H'); add("0000111", '1'); add("0001001", '.');

add("00000011", '5'); add("00000100", '6'); add("00000111", '7'); add("00001000", '8'); add("00001001", '9'); add("00001010", '0'); add("00001011", '4'); add("00000101", '-'); add("000000100", '('); add("000000101", ')');

Gerd

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

Hi Gerd Do you think there might be some form of escape sequence that is followed by a ref to the clear road names in Mdr 30..33. I noticed when looking at MapInstall manipulated Mdr that the '#' sort got changed. Ticker On Wed, 2021-12-15 at 11:13 +0000, Gerd Petermann wrote:

Hi Ticker,

this is what I have so far. The non-printable characters 0x01..0x04 are probably not correct. Note the special case with the last sequence. It only occurs once in the index and may as well be an error in the data. My code doesn't detect any unknown codes, so I think MDR16 must somehow contain this information. The character ž seems to appear both in upper and lower case?!? Might be wrong.

Hii Ticker, reg. MDR16: When I print the encoded characters which require 8 or more bits in the order of the Huffman tree they build a sequence which appears at the end of MDR 16 (last 60 bytes or so). Those chars which are encoded with fewer bits are still a mistery to me. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Mittwoch, 15. Dezember 2021 13:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Ticker, it's almost impossible to guess when there is only one entry in MDR 30/31 and only one occurence of the code "00000000000000000000". I used '#' in my debug code to mark an "unknown" char. A possible meaning could be that 30/31 are common prefixes and 32/33 are common suffixes in road names. I doubt that this is related to the Huffman encoding. Maybe the code "00000000000000000000" simply represents a special character that is replaced with a corresponding string in 30/31? No idea how that would work with the suffixes. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <ticker@jagIT.co.uk> Gesendet: Mittwoch, 15. Dezember 2021 12:47 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd Do you think there might be some form of escape sequence that is followed by a ref to the clear road names in Mdr 30..33. I noticed when looking at MapInstall manipulated Mdr that the '#' sort got changed. Ticker On Wed, 2021-12-15 at 11:13 +0000, Gerd Petermann wrote:

Hi Ticker,

this is what I have so far. The non-printable characters 0x01..0x04 are probably not correct. Note the special case with the last sequence. It only occurs once in the index and may as well be an error in the data. My code doesn't detect any unknown codes, so I think MDR16 must somehow contain this information. The character ž seems to appear both in upper and lower case?!? Might be wrong.

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

Hi Ticker, do you have a link for me? None of the methods to store the tree that I found would produce such a data structure. This is what I found so far: https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1208/assignments/ass... https://stackoverflow.com/questions/759707/efficient-way-of-storing-huffman-... Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 15. Dezember 2021 19:26 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd This could just be the way the tree has been flattened, with the data for longest sequences at the end, just happening to be byte aligned and without intervening bit markers to represent the tree because they have occurred already. regarding the 00000000000000s, maybe this a an escape followed by a fixed length index into Mdr 30/31 or whatever, and, as only 1 entry, it is zero, if there were more it could be 0000000000{fixedLenInxNotZero} Ticker On Wed, 2021-12-15 at 17:35 +0000, Gerd Petermann wrote:

Hii Ticker,

reg. MDR16: When I print the encoded characters which require 8 or more bits in the order of the Huffman tree they build a sequence which appears at the end of MDR 16 (last 60 bytes or so). Those chars which are encoded with fewer bits are still a mistery to me.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Mittwoch, 15. Dezember 2021 13:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit r572: MDR16 is some kind of codebook.

Hi Ticker,

it's almost impossible to guess when there is only one entry in MDR 30/31 and only one occurence of the code "00000000000000000000". I used '#' in my debug code to mark an "unknown" char.

A possible meaning could be that 30/31 are common prefixes and 32/33 are common suffixes in road names. I doubt that this is related to the Huffman encoding. Maybe the code "00000000000000000000" simply represents a special character that is replaced with a corresponding string in 30/31?

No idea how that would work with the suffixes. Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <ticker@jagIT.co.uk> Gesendet: Mittwoch, 15. Dezember 2021 12:47 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn]  Commit r572: MDR16 is some kind of codebook.

Hi Gerd

Do you think there might be some form of escape sequence that is followed by a ref to the clear road names in Mdr 30..33. I noticed when looking at MapInstall manipulated Mdr that the '#' sort got changed.

Ticker

On Wed, 2021-12-15 at 11:13 +0000, Gerd Petermann wrote:

...

Hi Ticker,

this is what I have so far. The non-printable characters 0x01..0x04 are probably not correct. Note the special case with the last sequence. It only occurs once in the index and may as well be an error in the data. My code doesn't detect any unknown codes, so I think MDR16 must somehow contain this information. The character ž seems to appear both in upper and lower case?!? Might be wrong.

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

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

Hi Ticker, the order of the chars seems to depend on the depth in the tree at which they appear. Something like this happens beginning at offset 5c in MDR 16: write 0x0b write 1st value at depth 5 write 0x0b write 2nd value at depth 5 write 0x0b write 3rd value at depth 5 ... write 0x0b write last value at depth 5 repeat 2 times: write 0x09 write 1st value at depth 4 repeat 2 times: write 0x09 write 2nd value at depth 4 ... repeat 2 times: write 0x09 write last value at depth 4 repeat 4 times: write 0x07 write 1st value at depth 3 (there is only one in this tree) No prefix, no repeats for the rest: write values at level depth 20 write values at level depth 19 ... write values at level depth 6 This decribes all bytes in MDR 16 from offset 5c to the end. No idea yet what the prefixes mean. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 16. Dezember 2021 10:04 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd I found similar/same algos. I'm trying to thing of other ways that might come up with what we see. I'll continue research. Ticker On Wed, 2021-12-15 at 20:18 +0000, Gerd Petermann wrote:

Hi Ticker,

do you have a link for me? None of the methods to store the tree that I found would produce such a data structure. This is what I found so far: https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1208/assignments/ass... https://stackoverflow.com/questions/759707/efficient-way-of-storing-huffman-...

Gerd

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

Hi Gerd I've followed the lists of chars at levels, some with separators, maybe indicate totally internal nodes. The early bit must be bit flags to describe the tree and maybe offsets into the leaves at different levels. The repeating at the low levels seems very strange. but wow - quite some detective work. Ticker On Thu, 2021-12-16 at 16:43 +0000, Gerd Petermann wrote:

Hi Ticker,

I looked at a few more old maps (donations from a mkgmap user) with MDR16. They all seem to match the pattern with the prefixes 0x0b, 0x09, and 0x07 and the repeating of information.

Maybe you get an idea what the rest means.

Gerd

________________________________________ Von: Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Donnerstag, 16. Dezember 2021 15:42 An: Development list for mkgmap Betreff: AW: [mkgmap-dev]       [mkgmap-svn]    Commit  r572:   MDR16   is      some    kind    of      codebook.

Hi Ticker,

the order of the chars seems to depend on the depth in the tree at which they appear. Something like this happens beginning at offset 5c in MDR 16: write 0x0b write 1st value at depth 5 write 0x0b write 2nd value at depth 5 write 0x0b write 3rd value at depth 5 ... write 0x0b write last value at depth 5

repeat 2 times: write 0x09 write 1st value at depth 4 repeat 2 times: write 0x09 write 2nd value at depth 4 ... repeat 2 times: write 0x09 write last value at depth 4

repeat 4 times: write 0x07 write 1st value at depth 3 (there is only one in this tree)

No prefix, no repeats for the rest: write values at level depth 20 write values at level depth 19 ... write values at level depth 6

This decribes all bytes in MDR 16 from offset 5c to the end.

No idea yet what the prefixes mean. Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 16. Dezember 2021 10:04 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit  r572:   MDR16   is      some    kind    of      codebook.

Hi Gerd

I found similar/same algos. I'm trying to thing of other ways that might come up with what we see. I'll continue research.

Ticker

On Wed, 2021-12-15 at 20:18 +0000, Gerd Petermann wrote:

...

Hi Ticker,

do you have a link for me? None of the methods to store the tree that I found would produce such a data structure. This is what I found so far: https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1208/assignments/ass... https://stackoverflow.com/questions/759707/efficient-way-of-storing-huffman-...

Gerd

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

Hi Ticker, sorry, my last post turned out to be wrong. The byte at offset 2 must have a different meaning. The previously posted mdr16 for benelux has a value of 2 but 4 bytes for the "struct", while the hungary map has a value of 2 and only 3 bytes for struct. Maybe the value for 3 / 4 can be calculated from the depth of the tree. I still have no idea what the values mean. I thought of some kind of raster image or a jump table but nothing worked out so far.. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Freitag, 17. Dezember 2021 09:20 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Ticker, found another pattern about the first bytes in Mdr16 (and again a loop from 20 down to 6) I noticed that the hex values 14,13,12,11,10,0f,...,06 appear with a distance of 5 bytes starting at offset 10 (0x0a). In maps where the 2nd byte is 2 instead of 3 the distance is 4 and the offset is 9. Possible interpretation is below, this also works with other maps. Note that in the 2nd tree level 10 is missing. This would explain why the counters are needed. --------- MDR 16 (decompression codebook Huffman tree) ------------------------- 000002b6 | 000000 | 4a | ??? 000002b7 | 000001 | 03 | bytes for struct: 3 + 1 = 4 000002b8 | 000002 | 15 | ??? 000002b9 | 000003 | 14 | 1st level with struct: 20 000002ba | 000004 | 0f 08 85 00 00 00 | ??? 000002c0 | 00000a | 14 | struct level: 20 000002c1 | 00000b | 00 06 00 00 | struct for 20 000002c5 | 00000f | 13 | struct level: 19 000002c6 | 000010 | 06 18 00 00 | struct for 19 000002ca | 000014 | 12 | struct level: 18 000002cb | 000015 | 0f 30 00 00 | struct for 18 000002cf | 000019 | 11 | struct level: 17 000002d0 | 00001a | 15 50 00 00 | struct for 17 000002d4 | 00001e | 10 | struct level: 16 000002d5 | 00001f | 19 80 00 00 | struct for 16 000002d9 | 000023 | 0f | struct level: 15 000002da | 000024 | 1c c0 00 00 | struct for 15 000002de | 000028 | 0e | struct level: 14 000002df | 000029 | 1e 00 02 00 | struct for 14 000002e3 | 00002d | 0d | struct level: 13 000002e4 | 00002e | 23 00 03 00 | struct for 13 000002e8 | 000032 | 0c | struct level: 12 000002e9 | 000033 | 25 00 06 00 | struct for 12 000002ed | 000037 | 0b | struct level: 11 000002ee | 000038 | 28 00 0c 00 | struct for 11 000002f2 | 00003c | 0a | struct level: 10 000002f3 | 00003d | 2b 00 10 00 | struct for 10 000002f7 | 000041 | 09 | struct level: 9 000002f8 | 000042 | 2c 00 30 00 | struct for 9 000002fc | 000046 | 08 | struct level: 8 000002fd | 000047 | 30 00 c0 00 | struct for 8 00000301 | 00004b | 07 | struct level: 7 00000302 | 00004c | 39 00 40 01 | struct for 7 00000306 | 000050 | 06 | struct level: 6 00000307 | 000051 | 3d 00 0c 18 | struct for 6 smaller tree (TopoGuide Hungary with codepage 1250): 0000030e | 000000 | 8e | ??? 0000030f | 000001 | 02 | bytes for struct: 2 + 1 = 3 00000310 | 000002 | 15 | ??? 00000311 | 000003 | 10 | 1st level with struct: 16 00000312 | 000004 | 0a 08 6d 00 00 | ??? 00000317 | 000009 | 10 | struct level: 16 00000318 | 00000a | 00 06 00 | struct for 16 0000031b | 00000d | 0f | struct level: 15 0000031c | 00000e | 06 14 00 | struct for 15 0000031f | 000011 | 0e | struct level: 14 00000320 | 000012 | 0d 38 00 | struct for 14 00000323 | 000015 | 0d | struct level: 13 00000324 | 000016 | 16 70 00 | struct for 13 00000327 | 000019 | 0c | struct level: 12 00000328 | 00001a | 1d a0 00 | struct for 12 0000032b | 00001d | 0b | struct level: 11 0000032c | 00001e | 20 00 01 | struct for 11 0000032f | 000021 | 09 | struct level: 9 00000330 | 000022 | 23 00 02 | struct for 9 00000333 | 000025 | 08 | struct level: 8 00000334 | 000026 | 25 00 04 | struct for 8 00000337 | 000029 | 07 | struct level: 7 00000338 | 00002a | 27 00 0c | struct for 7 0000033b | 00002d | 06 | struct level: 6 0000033c | 00002e | 2b 00 08 | struct for 6 | | | Unknown 165 bytes: 0000030e | 000000 | 8e 02 15 10 0a 08 6d 00 | �.....m. 00000316 | 000008 | 00 10 00 06 00 0f 06 14 | ........ 0000031e | 000010 | 00 0e 0d 38 00 0d 16 70 | ...8...p 00000326 | 000018 | 00 0c 1d a0 00 0b 20 00 | ... .. . 0000032e | 000020 | 01 09 23 00 02 08 25 00 | ..#...%. 00000336 | 000028 | 04 07 27 00 0c 06 2b 00 | ..'...+. 0000033e | 000030 | 08 10 09 12 09 12 09 12 | ........ 00000346 | 000038 | 09 12 09 12 09 0b 59 0b | ......Y. 0000034e | 000040 | 47 0b 49 0b c1 0b 5a 0b | G.I.�.Z. 00000356 | 000048 | 4b 0b 44 0b 4f 0b 4e 09 | K.D.O.N. 0000035e | 000050 | 54 09 54 09 41 09 41 09 | T.T.A.A. 00000366 | 000058 | 53 09 53 09 45 09 45 09 | S.S.E.E. 0000036e | 000060 | 4c 09 4c 09 52 09 52 07 | L.L.R.R. 00000376 | 000068 | 00 07 00 07 00 07 00 33 | .......3 0000037e | 000070 | 34 37 9d c5 de 32 36 38 | 47���268 00000386 | 000078 | 51 ad c2 ce 27 31 5f 28 | Q���'1_( 0000038e | 000080 | aa c4 29 cf d0 57 9e ba | ��)��W�� 00000396 | 000088 | c3 c6 d2 dd 58 be 2c 8a | ����X�,� 0000039e | 000090 | c8 2e cd db da dc 4a 20 | �.����J 000003a6 | 000098 | 46 2d 42 43 50 c9 55 4d | F-BCP�UM 000003ae | 0000a0 | d3 d5 d6 48 56 | ���HV Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 16. Dezember 2021 18:33 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd I've followed the lists of chars at levels, some with separators, maybe indicate totally internal nodes. The early bit must be bit flags to describe the tree and maybe offsets into the leaves at different levels. The repeating at the low levels seems very strange. but wow - quite some detective work. Ticker On Thu, 2021-12-16 at 16:43 +0000, Gerd Petermann wrote:

Hi Ticker,

I looked at a few more old maps (donations from a mkgmap user) with MDR16. They all seem to match the pattern with the prefixes 0x0b, 0x09, and 0x07 and the repeating of information.

Maybe you get an idea what the rest means.

Gerd

________________________________________ Von: Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Donnerstag, 16. Dezember 2021 15:42 An: Development list for mkgmap Betreff: AW: [mkgmap-dev]������ [mkgmap-svn]��� Commit r572: MDR16 is some kind of codebook.

Hi Ticker,

the order of the chars seems to depend on the depth in the tree at which they appear. Something like this happens beginning at offset 5c in MDR 16: write 0x0b write 1st value at depth 5 write 0x0b write 2nd value at depth 5 write 0x0b write 3rd value at depth 5 ... write 0x0b write last value at depth 5

repeat 2 times: write 0x09 write 1st value at depth 4 repeat 2 times: write 0x09 write 2nd value at depth 4 ... repeat 2 times: write 0x09 write last value at depth 4

repeat 4 times: write 0x07 write 1st value at depth 3 (there is only one in this tree)

No prefix, no repeats for the rest: write values at level depth 20 write values at level depth 19 ... write values at level depth 6

This decribes all bytes in MDR 16 from offset 5c to the end.

No idea yet what the prefixes mean. Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 16. Dezember 2021 10:04 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]������ [mkgmap-svn]��� Commit r572: MDR16 is some kind of codebook.

Hi Gerd

I found similar/same algos. I'm trying to thing of other ways that might come up with what we see. I'll continue research.

Ticker

On Wed, 2021-12-15 at 20:18 +0000, Gerd Petermann wrote:

...

Hi Ticker,

do you have a link for me? None of the methods to store the tree that I found would produce such a data structure. This is what I found so far: https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1208/assignments/ass... https://stackoverflow.com/questions/759707/efficient-way-of-storing-huffman-...

Gerd

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

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

Hi Ticker, maybe the table allows to decode the strings faster or someone very unexperienced invented the code or it's intended obfuscation or Garmin took an algo that was meant for something else and what we see is partly ignored. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Samstag, 18. Dezember 2021 11:52 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd I'm amazed at how they've made something that could be simple and expressed with a few byte of control, around 140 bits for tree structure and 80 or so bytes of characters so big and complex! Maybe the few (5) layers closest to the root somehow hard coded. Where a node has a sub-tree on one side and a letter on the other, are these always the same way round, such that the these will always tend to one side of the tree, with nothing beyond because of double leaves closer to the root stop the tree. This would allow reasonable length bit sequences to describe the structure at each level, rather than it growing by powers of 2. Ticker On Sat, 2021-12-18 at 10:19 +0000, Gerd Petermann wrote:

Hi Ticker,

sorry, my last post turned out to be wrong. The byte at offset 2 must have a different meaning. The previously posted mdr16 for benelux has a value of 2 but 4 bytes for the "struct", while the hungary map has a value of 2 and only 3 bytes for struct. Maybe the value for 3 / 4 can be calculated from the depth of the tree.

I still have no idea what the values mean. I thought of some kind of raster image or a jump table but nothing worked out so far..

Gerd

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

Hi Ticker, my thought for the struct bytes was that the 1-bits might represent the position of leafs, but the bit counts don't match. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Sonntag, 19. Dezember 2021 10:12 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd It looks like the order of the letter patterns approaches canonical Huffman (but not quite as far as I can see). With this, only the number of codes of each length is required to form the tree. The "struct for {level}" looks like 2 numbers. Both increasing as levels go from 20 to 6. The first, a single byte from #00 to #3d - this could be give the accumulated lengths at each level (but I didn't get it to match). The second, variable length, from #000006 to #180c00 and I've no idea what it could mean. Levels 1 - 5 seem to be handled differently. with the repeat * 4, repeat * 2, no repeat and the padding. Ticker _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Ticker, please explain. What counters do you see? What do they mean? Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 20. Dezember 2021 09:49 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd The tree is arranged so that letters at any level always have the highest values, ie come in from the right, and there are no gaps so no need for bit-flags. All it needs is the count of letters at each level to determine the tree. For levels 7 to 18 this is consistent and the count can be determined from the first byte in the "struct for {level}". Levels 19 and 20 are slightly out, but I think you found some strangeness here, including something indicate using Mdr3x data. Level 6 count might be mixed into the following I haven't been able to work out levels 1-5 yet, but somewhere would hope to find counts 0,0,1,7,9 maybe cumulative, maybe backwards, maybe without the first 2 values, maybe starting from the cumulative level 6 value. Ticker On Sun, 2021-12-19 at 21:12 +0000, Gerd Petermann wrote:

Hi Ticker,

my thought for the struct bytes was that the 1-bits might represent the position of leafs, but the bit counts don't match.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Sonntag, 19. Dezember 2021 10:12 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit r572: MDR16 is some kind of codebook.

Hi Gerd

It looks like the order of the letter patterns approaches canonical Huffman (but not quite as far as I can see). With this, only the number of codes of each length is required to form the tree.

The "struct for {level}" looks like 2 numbers. Both increasing as levels go from 20 to 6. The first, a single byte from #00 to #3d - this could be give the accumulated lengths at each level (but I didn't get it to match). The second, variable length, from #000006 to #180c00 and I've no idea what it could mean.

Levels 1 - 5 seem to be handled differently. with the repeat * 4, repeat * 2, no repeat and the padding.

Ticker

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

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

Hi Ticker, OK, I see. It seems to work out for most of the delta values. Deltas are 6,9,6,4,3,2,5,2,3,3,1,4,9,4 I'll try to find out if I can modify the tree so that it matches all numbers. Probably sometimes I found too short codes. Good finding! Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 20. Dezember 2021 10:38 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd Are you OK with the idea of the letters at any level being to the right. Then the letters at this level take decreasing values. When exhausted, the next lower slot will be the start of the next level, so subtract 1 to find it and append '1' to the bit-string to get the starting position for the next level. in the test map there is, say: 000002cf | 000019 | 11 | struct level: 17 000002d0 | 00001a | 15 50 00 00 | struct for 17 000002d4 | 00001e | 10 | struct level: 16 000002d5 | 00001f | 19 80 00 00 | struct for 16 000002d9 | 000023 | 0f | struct level: 15 000002da | 000024 | 1c c0 00 00 | struct for 15 The differences between the first byte after the level indicator ie 15, 19 & 1c) give 4 and 3, which are the number of letters at level 17 and level 16 Ticker On Mon, 2021-12-20 at 09:18 +0000, Gerd Petermann wrote:

Hi Ticker, please explain. What counters do you see? What do they mean?

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 20. Dezember 2021 09:49 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit r572: MDR16 is some kind of codebook.

Hi Gerd

The tree is arranged so that letters at any level always have the highest values, ie come in from the right, and there are no gaps so no need for bit-flags. All it needs is the count of letters at each level to determine the tree.

For levels 7 to 18 this is consistent and the count can be determined from the first byte in the "struct for {level}".

Levels 19 and 20 are slightly out, but I think you found some strangeness here, including something indicate using Mdr3x data.

Level 6 count might be mixed into the following

I haven't been able to work out levels 1-5 yet, but somewhere would hope to find counts 0,0,1,7,9 maybe cumulative, maybe backwards, maybe without the first 2 values, maybe starting from the cumulative level 6 value.

Ticker

On Sun, 2021-12-19 at 21:12 +0000, Gerd Petermann wrote:

...

Hi Ticker,

my thought for the struct bytes was that the 1-bits might represent the position of leafs, but the bit counts don't match.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Sonntag, 19. Dezember 2021 10:12 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit r572: MDR16 is some kind of codebook.

Hi Gerd

It looks like the order of the letter patterns approaches canonical Huffman (but not quite as far as I can see). With this, only the number of codes of each length is required to form the tree.

The "struct for {level}" looks like 2 numbers. Both increasing as levels go from 20 to 6. The first, a single byte from #00 to #3d - this could be give the accumulated lengths at each level (but I didn't get it to match). The second, variable length, from #000006 to #180c00 and I've no idea what it could mean.

Levels 1 - 5 seem to be handled differently. with the repeat * 4, repeat * 2, no repeat and the padding.

Ticker

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

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

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

Hi Ticker, looks good. With your hints I was able to write a patch for MdrDisplay that seems able to decode compressed mdr15 for my maps which have mdr 16 section. Maybe you have another map... It also changes some details for mdr 30/31 and 32/33. Open problem is the length of the gap between the end of data for the 6th level and the first bytes for level 5 (prefix 0b). I see either 7 or 12 or 5 bytes. Check the code that calculdates value for variable skip. The values might not at all depend on the depth of the tree. Code is not at all optimized, it just started to work for me. Lots of bytes in MDR 16 are ignored. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Montag, 20. Dezember 2021 11:29 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Ticker, yes, with your theory I found errors in my code. Here's the corrected version // depth 3, prefix 0x07 addHuffmanNode("111", 'A'); // depth 4, prefix 0x09 addHuffmanNode("0111", '\0'); // 0x00 addHuffmanNode("1000", ' '); //0x20 addHuffmanNode("1001", 'E'); addHuffmanNode("1010", 'N'); addHuffmanNode("1011", 'O'); addHuffmanNode("1100", 'I'); addHuffmanNode("1101", 'R'); // depth 5, prefix 0x0b addHuffmanNode("00101", 'C'); addHuffmanNode("00110", 'S'); addHuffmanNode("00111", 'D'); addHuffmanNode("01000", 'T'); addHuffmanNode("01001", 'M'); addHuffmanNode("01010", 'V'); addHuffmanNode("01011", 'J'); addHuffmanNode("01100", 'K'); addHuffmanNode("01101", 'L'); // depth 6 addHuffmanNode("000101", 'G'); addHuffmanNode("000110", 'Z'); addHuffmanNode("000111", 'U'); addHuffmanNode("001000", 'P'); addHuffmanNode("001001", 'B'); // depth 7 addHuffmanNode("0000110", 'H'); addHuffmanNode("0000111", '1'); addHuffmanNode("0001000", '2'); addHuffmanNode("0001001", '.'); // depth 8 addHuffmanNode("00000011", '5'); addHuffmanNode("00000100", '6'); addHuffmanNode("00000101", '-'); addHuffmanNode("00000110", '7'); addHuffmanNode("00000111", '3'); addHuffmanNode("00001000", '8'); addHuffmanNode("00001001", '9'); addHuffmanNode("00001010", '0'); addHuffmanNode("00001011", '4'); // depth 9 addHuffmanNode("000000010", 'F'); addHuffmanNode("000000011",','); addHuffmanNode("000000100", '('); addHuffmanNode("000000101", ')'); // depth 10 addHuffmanNode("0000000011", '*'); // depth 11 addHuffmanNode("00000000011", 'Y'); addHuffmanNode("00000000100", '"'); addHuffmanNode("00000000101", (char) 0x06); // non-print4 // depth 12 addHuffmanNode("000000000011", 'W'); addHuffmanNode("000000000100", 'X'); addHuffmanNode("000000000101", (char) 0x05); //non-print some shield code // depth 13 addHuffmanNode("0000000000100", '&'); addHuffmanNode("0000000000101", (char) 0x1f); //non-print2 // depth 14 addHuffmanNode("00000000000011", 'Q'); addHuffmanNode("00000000000100", 'Š'); addHuffmanNode("00000000000101", '\''); // mdr16 says 0x8a addHuffmanNode("00000000000110", 'Ë'); addHuffmanNode("00000000000111", '/'); // depth 15 addHuffmanNode("000000000000100", 'Æ'); addHuffmanNode("000000000000101", 'È'); // depth 16 addHuffmanNode("0000000000000101", (char) 0x04); // non-print3 addHuffmanNode("0000000000000110", '!'); addHuffmanNode("0000000000000111", (char) 0x9e); //Ž // depth 17 addHuffmanNode("00000000000000110",'+'); addHuffmanNode("00000000000000111", '–'); // different to minus mdr16: 0x96 addHuffmanNode("00000000000001000", 'Á'); //Á addHuffmanNode("00000000000001001", 'Ü'); // depth 18 addHuffmanNode("000000000000000110", '_'); addHuffmanNode("000000000000000111", '{'); addHuffmanNode("000000000000001000", '“'); // mdr16: 0x93 addHuffmanNode("000000000000001001", 'É'); addHuffmanNode("000000000000001010", 'Ð'); addHuffmanNode("000000000000001011", 'Ö'); // depth 19 addHuffmanNode("0000000000000000011", '?'); addHuffmanNode("0000000000000000100", '`'); // mdr16: 0x60 addHuffmanNode("0000000000000000101", '„'); // mdr16: 0x84 addHuffmanNode("0000000000000000110", 'ž'); // mdr16: 0x8e addHuffmanNode("0000000000000000111", '’'); // mdr16: 0x92 addHuffmanNode("0000000000000001000", 'Ä'); addHuffmanNode("0000000000000001001", 'Ø'); addHuffmanNode("0000000000000001010", 'Ú'); addHuffmanNode("0000000000000001011", 'Û'); // depth 20 addHuffmanNode("00000000000000000000", '#'); // offset into MDR 30/31? MapSource displays "HWY " addHuffmanNode("00000000000000000001", '%'); // addHuffmanNode("00000000000000000010", ':'); addHuffmanNode("00000000000000000011", ';'); addHuffmanNode("00000000000000000100", (char) 0x8f); addHuffmanNode("00000000000000000101", (char) 0xb8); Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Montag, 20. Dezember 2021 10:59 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Ticker, OK, I see. It seems to work out for most of the delta values. Deltas are 6,9,6,4,3,2,5,2,3,3,1,4,9,4 I'll try to find out if I can modify the tree so that it matches all numbers. Probably sometimes I found too short codes. Good finding! Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 20. Dezember 2021 10:38 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd Are you OK with the idea of the letters at any level being to the right. Then the letters at this level take decreasing values. When exhausted, the next lower slot will be the start of the next level, so subtract 1 to find it and append '1' to the bit-string to get the starting position for the next level. in the test map there is, say: 000002cf | 000019 | 11 | struct level: 17 000002d0 | 00001a | 15 50 00 00 | struct for 17 000002d4 | 00001e | 10 | struct level: 16 000002d5 | 00001f | 19 80 00 00 | struct for 16 000002d9 | 000023 | 0f | struct level: 15 000002da | 000024 | 1c c0 00 00 | struct for 15 The differences between the first byte after the level indicator ie 15, 19 & 1c) give 4 and 3, which are the number of letters at level 17 and level 16 Ticker On Mon, 2021-12-20 at 09:18 +0000, Gerd Petermann wrote:

Hi Ticker, please explain. What counters do you see? What do they mean?

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 20. Dezember 2021 09:49 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit r572: MDR16 is some kind of codebook.

Hi Gerd

The tree is arranged so that letters at any level always have the highest values, ie come in from the right, and there are no gaps so no need for bit-flags. All it needs is the count of letters at each level to determine the tree.

For levels 7 to 18 this is consistent and the count can be determined from the first byte in the "struct for {level}".

Levels 19 and 20 are slightly out, but I think you found some strangeness here, including something indicate using Mdr3x data.

Level 6 count might be mixed into the following

I haven't been able to work out levels 1-5 yet, but somewhere would hope to find counts 0,0,1,7,9 maybe cumulative, maybe backwards, maybe without the first 2 values, maybe starting from the cumulative level 6 value.

Ticker

On Sun, 2021-12-19 at 21:12 +0000, Gerd Petermann wrote:

...

Hi Ticker,

my thought for the struct bytes was that the 1-bits might represent the position of leafs, but the bit counts don't match.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Sonntag, 19. Dezember 2021 10:12 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit r572: MDR16 is some kind of codebook.

Hi Gerd

It looks like the order of the letter patterns approaches canonical Huffman (but not quite as far as I can see). With this, only the number of codes of each length is required to form the tree.

The "struct for {level}" looks like 2 numbers. Both increasing as levels go from 20 to 6. The first, a single byte from #00 to #3d - this could be give the accumulated lengths at each level (but I didn't get it to match). The second, variable length, from #000006 to #180c00 and I've no idea what it could mean.

Levels 1 - 5 seem to be handled differently. with the repeat * 4, repeat * 2, no repeat and the padding.

Ticker

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

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

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

Hi Ticker, I also thought that some bytes may tells us the uncompressed size or frequencies. I don't see any clear pattern so far... Some number for the Adria Topo Map: (Mdr 16 length 212) Uncompressed size: 1.582.655 (0x18263e) , compressed: 1029077 (0x0fb3d5) Frequencies of the tree nodes: '' 0x3 freq: 1 (0x1) '%' 0x25 freq: 1 (0x1) ':' 0x3a freq: 1 (0x1) ';' 0x3b freq: 1 (0x1) '�' 0xfd freq: 1 (0x1) '¸' 0xb8 freq: 1 (0x1) '?' 0x3f freq: 2 (0x2) '`' 0x60 freq: 2 (0x2) '„' 0x1e freq: 2 (0x2) 'Ž' 0x7d freq: 3 (0x3) '’' 0x19 freq: 2 (0x2) 'Ä' 0xc4 freq: 2 (0x2) 'Ø' 0xd8 freq: 2 (0x2) 'Ú' 0xda freq: 1 (0x1) 'Û' 0xdb freq: 2 (0x2) '_' 0x5f freq: 4 (0x4) '{' 0x7b freq: 6 (0x6) '“' 0x1c freq: 4 (0x4) 'É' 0xc9 freq: 4 (0x4) 'Ð' 0xd0 freq: 5 (0x5) 'Ö' 0xd6 freq: 5 (0x5) '+' 0x2b freq: 7 (0x7) '–' 0x13 freq: 12 (0xc) 'Á' 0xc1 freq: 6 (0x6) 'Ü' 0xdc freq: 9 (0x9) '' 0x4 freq: 19 (0x13) '!' 0x21 freq: 18 (0x12) 'ž' 0x7e freq: 15 (0xf) 'Æ' 0xc6 freq: 43 (0x2b) 'È' 0xc8 freq: 34 (0x22) 'Q' 0x51 freq: 80 (0x50) 'Š' 0x60 freq: 49 (0x31) ''' 0x27 freq: 95 (0x5f) 'Ë' 0xcb freq: 51 (0x33) '/' 0x2f freq: 64 (0x40) '&' 0x26 freq: 153 (0x99) '' 0x1f freq: 195 (0xc3) 'W' 0x57 freq: 294 (0x126) 'X' 0x58 freq: 422 (0x1a6) '' 0x5 freq: 242 (0xf2) 'Y' 0x59 freq: 719 (0x2cf) '"' 0x22 freq: 614 (0x266) '' 0x6 freq: 842 (0x34a) '*' 0x2a freq: 1905 (0x771) 'F' 0x46 freq: 4481 (0x1181) ',' 0x2c freq: 2126 (0x84e) '(' 0x28 freq: 2537 (0x9e9) ')' 0x29 freq: 2558 (0x9fe) '5' 0x35 freq: 6778 (0x1a7a) '6' 0x36 freq: 6634 (0x19ea) '-' 0x2d freq: 6588 (0x19bc) '7' 0x37 freq: 5972 (0x1754) '3' 0x33 freq: 7478 (0x1d36) '8' 0x38 freq: 5832 (0x16c8) '9' 0x39 freq: 5314 (0x14c2) '0' 0x30 freq: 6539 (0x198b) '4' 0x34 freq: 7203 (0x1c23) 'H' 0x48 freq: 12992 (0x32c0) '1' 0x31 freq: 13281 (0x33e1) '2' 0x32 freq: 8713 (0x2209) '.' 0x2e freq: 10184 (0x27c8) 'G' 0x47 freq: 24930 (0x6162) 'Z' 0x5a freq: 23284 (0x5af4) 'U' 0x55 freq: 31985 (0x7cf1) 'P' 0x50 freq: 34866 (0x8832) 'B' 0x42 freq: 33286 (0x8206) 'C' 0x43 freq: 66619 (0x1043b) 'S' 0x53 freq: 71047 (0x11587) 'D' 0x44 freq: 37462 (0x9256) 'T' 0x54 freq: 53719 (0xd1d7) 'M' 0x4d freq: 40220 (0x9d1c) 'V' 0x56 freq: 63113 (0xf689) 'J' 0x4a freq: 44778 (0xaeea) 'K' 0x4b freq: 63856 (0xf970) 'L' 0x4c freq: 63057 (0xf651) '' 0x0 freq: 108543 (0x1a7ff) ' ' 0x20 freq: 139214 (0x21fce) 'E' 0x45 freq: 99070 (0x182fe) 'N' 0x4e freq: 79383 (0x13617) 'O' 0x4f freq: 101405 (0x18c1d) 'I' 0x49 freq: 113012 (0x1b974) 'R' 0x52 freq: 95298 (0x17442) 'A' 0x41 freq: 181900 (0x2c68c) Maybe you find something new? Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Dienstag, 21. Dezember 2021 17:49 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Ticker, looks good. With your hints I was able to write a patch for MdrDisplay that seems able to decode compressed mdr15 for my maps which have mdr 16 section. Maybe you have another map... It also changes some details for mdr 30/31 and 32/33. Open problem is the length of the gap between the end of data for the 6th level and the first bytes for level 5 (prefix 0b). I see either 7 or 12 or 5 bytes. Check the code that calculdates value for variable skip. The values might not at all depend on the depth of the tree. Code is not at all optimized, it just started to work for me. Lots of bytes in MDR 16 are ignored. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Montag, 20. Dezember 2021 11:29 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Ticker, yes, with your theory I found errors in my code. Here's the corrected version // depth 3, prefix 0x07 addHuffmanNode("111", 'A'); // depth 4, prefix 0x09 addHuffmanNode("0111", '\0'); // 0x00 addHuffmanNode("1000", ' '); //0x20 addHuffmanNode("1001", 'E'); addHuffmanNode("1010", 'N'); addHuffmanNode("1011", 'O'); addHuffmanNode("1100", 'I'); addHuffmanNode("1101", 'R'); // depth 5, prefix 0x0b addHuffmanNode("00101", 'C'); addHuffmanNode("00110", 'S'); addHuffmanNode("00111", 'D'); addHuffmanNode("01000", 'T'); addHuffmanNode("01001", 'M'); addHuffmanNode("01010", 'V'); addHuffmanNode("01011", 'J'); addHuffmanNode("01100", 'K'); addHuffmanNode("01101", 'L'); // depth 6 addHuffmanNode("000101", 'G'); addHuffmanNode("000110", 'Z'); addHuffmanNode("000111", 'U'); addHuffmanNode("001000", 'P'); addHuffmanNode("001001", 'B'); // depth 7 addHuffmanNode("0000110", 'H'); addHuffmanNode("0000111", '1'); addHuffmanNode("0001000", '2'); addHuffmanNode("0001001", '.'); // depth 8 addHuffmanNode("00000011", '5'); addHuffmanNode("00000100", '6'); addHuffmanNode("00000101", '-'); addHuffmanNode("00000110", '7'); addHuffmanNode("00000111", '3'); addHuffmanNode("00001000", '8'); addHuffmanNode("00001001", '9'); addHuffmanNode("00001010", '0'); addHuffmanNode("00001011", '4'); // depth 9 addHuffmanNode("000000010", 'F'); addHuffmanNode("000000011",','); addHuffmanNode("000000100", '('); addHuffmanNode("000000101", ')'); // depth 10 addHuffmanNode("0000000011", '*'); // depth 11 addHuffmanNode("00000000011", 'Y'); addHuffmanNode("00000000100", '"'); addHuffmanNode("00000000101", (char) 0x06); // non-print4 // depth 12 addHuffmanNode("000000000011", 'W'); addHuffmanNode("000000000100", 'X'); addHuffmanNode("000000000101", (char) 0x05); //non-print some shield code // depth 13 addHuffmanNode("0000000000100", '&'); addHuffmanNode("0000000000101", (char) 0x1f); //non-print2 // depth 14 addHuffmanNode("00000000000011", 'Q'); addHuffmanNode("00000000000100", 'Š'); addHuffmanNode("00000000000101", '\''); // mdr16 says 0x8a addHuffmanNode("00000000000110", 'Ë'); addHuffmanNode("00000000000111", '/'); // depth 15 addHuffmanNode("000000000000100", 'Æ'); addHuffmanNode("000000000000101", 'È'); // depth 16 addHuffmanNode("0000000000000101", (char) 0x04); // non-print3 addHuffmanNode("0000000000000110", '!'); addHuffmanNode("0000000000000111", (char) 0x9e); //Ž // depth 17 addHuffmanNode("00000000000000110",'+'); addHuffmanNode("00000000000000111", '–'); // different to minus mdr16: 0x96 addHuffmanNode("00000000000001000", 'Á'); //Á addHuffmanNode("00000000000001001", 'Ü'); // depth 18 addHuffmanNode("000000000000000110", '_'); addHuffmanNode("000000000000000111", '{'); addHuffmanNode("000000000000001000", '“'); // mdr16: 0x93 addHuffmanNode("000000000000001001", 'É'); addHuffmanNode("000000000000001010", 'Ð'); addHuffmanNode("000000000000001011", 'Ö'); // depth 19 addHuffmanNode("0000000000000000011", '?'); addHuffmanNode("0000000000000000100", '`'); // mdr16: 0x60 addHuffmanNode("0000000000000000101", '„'); // mdr16: 0x84 addHuffmanNode("0000000000000000110", 'ž'); // mdr16: 0x8e addHuffmanNode("0000000000000000111", '’'); // mdr16: 0x92 addHuffmanNode("0000000000000001000", 'Ä'); addHuffmanNode("0000000000000001001", 'Ø'); addHuffmanNode("0000000000000001010", 'Ú'); addHuffmanNode("0000000000000001011", 'Û'); // depth 20 addHuffmanNode("00000000000000000000", '#'); // offset into MDR 30/31? MapSource displays "HWY " addHuffmanNode("00000000000000000001", '%'); // addHuffmanNode("00000000000000000010", ':'); addHuffmanNode("00000000000000000011", ';'); addHuffmanNode("00000000000000000100", (char) 0x8f); addHuffmanNode("00000000000000000101", (char) 0xb8); Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Montag, 20. Dezember 2021 10:59 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Ticker, OK, I see. It seems to work out for most of the delta values. Deltas are 6,9,6,4,3,2,5,2,3,3,1,4,9,4 I'll try to find out if I can modify the tree so that it matches all numbers. Probably sometimes I found too short codes. Good finding! Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 20. Dezember 2021 10:38 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd Are you OK with the idea of the letters at any level being to the right. Then the letters at this level take decreasing values. When exhausted, the next lower slot will be the start of the next level, so subtract 1 to find it and append '1' to the bit-string to get the starting position for the next level. in the test map there is, say: 000002cf | 000019 | 11 | struct level: 17 000002d0 | 00001a | 15 50 00 00 | struct for 17 000002d4 | 00001e | 10 | struct level: 16 000002d5 | 00001f | 19 80 00 00 | struct for 16 000002d9 | 000023 | 0f | struct level: 15 000002da | 000024 | 1c c0 00 00 | struct for 15 The differences between the first byte after the level indicator ie 15, 19 & 1c) give 4 and 3, which are the number of letters at level 17 and level 16 Ticker On Mon, 2021-12-20 at 09:18 +0000, Gerd Petermann wrote:

Hi Ticker, please explain. What counters do you see? What do they mean?

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 20. Dezember 2021 09:49 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit r572: MDR16 is some kind of codebook.

Hi Gerd

The tree is arranged so that letters at any level always have the highest values, ie come in from the right, and there are no gaps so no need for bit-flags. All it needs is the count of letters at each level to determine the tree.

For levels 7 to 18 this is consistent and the count can be determined from the first byte in the "struct for {level}".

Levels 19 and 20 are slightly out, but I think you found some strangeness here, including something indicate using Mdr3x data.

Level 6 count might be mixed into the following

I haven't been able to work out levels 1-5 yet, but somewhere would hope to find counts 0,0,1,7,9 maybe cumulative, maybe backwards, maybe without the first 2 values, maybe starting from the cumulative level 6 value.

Ticker

On Sun, 2021-12-19 at 21:12 +0000, Gerd Petermann wrote:

...

Hi Ticker,

my thought for the struct bytes was that the 1-bits might represent the position of leafs, but the bit counts don't match.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Sonntag, 19. Dezember 2021 10:12 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit r572: MDR16 is some kind of codebook.

Hi Gerd

It looks like the order of the letter patterns approaches canonical Huffman (but not quite as far as I can see). With this, only the number of codes of each length is required to form the tree.

The "struct for {level}" looks like 2 numbers. Both increasing as levels go from 20 to 6. The first, a single byte from #00 to #3d - this could be give the accumulated lengths at each level (but I didn't get it to match). The second, variable length, from #000006 to #180c00 and I've no idea what it could mean.

Levels 1 - 5 seem to be handled differently. with the repeat * 4, repeat * 2, no repeat and the padding.

Ticker

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

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

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

Hi Ticker, I think those are the two that I didn't post before. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 22. Dezember 2021 12:32 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd Can you send me the Mdr16 display of some of the other maps you've been looking at. I'd like to try and find some meaning for bytes 0..2 and the prefix before the level 5 data. Thanks Ticker On Wed, 2021-12-22 at 08:43 +0000, Gerd Petermann wrote:

Hi Ticker,

I also thought that some bytes may tells us the uncompressed size or frequencies. I don't see any clear pattern so far...

Some number for the Adria Topo Map: (Mdr 16 length 212) Uncompressed size: 1.582.655 (0x18263e) , compressed: 1029077 (0x0fb3d5) Frequencies of the tree nodes:

'' 0x3 freq: 1 (0x1) '%' 0x25 freq: 1 (0x1) ':' 0x3a freq: 1 (0x1)

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

Hi Gerd I guessed that it was the \0 that cut the file off. You mean something like answer 5 here: https://stackoverflow.com/questions/759707/efficient-way-of-storing-huffman-... I looked at this earlier trying to work out if it was relevant but didn't make it fit - I should have tried harder. I still haven't spotted anything to determine the length of the 2 /3 byte in before and in the struct for {length} Ticker On Thu, 2021-12-23 at 01:17 +0000, Gerd Petermann wrote:

Hi Ticker,

sorry, just noticed that something went wrong with copy&paste because of the \0 character. Anyway, I think I understand the meaning of the part with the prefixes. I assume that Garmin reads the first 5 bits and uses this value as an index into a table which directly follows the first array. This 2nd table is a 32x2 lookup table, where the 2nd byte gives the value and the first byte some kind of status info which is used to position the bit reader. This would explain the repeating characters. Something like this:

--------- MDR 16 (decompression codebook Huffman tree) ---------------- --------- 000002b6 | 000000 | 4a                      | ???

Hi Gerd Maybe the "is always 8" is the character width. I think I understand parts of it. Read 5 bits and look up, giving 2 bytes. if first 3/5/6/9/b the final char in the second byte and return (b- first)/2 to the bit stream. Otherwise the combination somehow indicate a minimum number of more bits to read and where to start searching. maybe the 'struct for level' 1 or 2 bytes is a bit flag of which levels to look in. I notice (in topo_fr) it is normally a single or adjacent bits except for 0xa, but there are no chars at level 19 prefix 0 doesn't quite follow the rules Ticker On Thu, 2021-12-23 at 09:40 +0000, Gerd Petermann wrote:

Hi Ticker,

ouch, didn't even read that one :(  Would have saved me a lot of time as my first idea was a "jump table". Attached is the new patch and the corrected mdr16 outputs produced with this patch.

So, besides the fields with ??? the only open question is the meaning of the struct bytes in the first table. I guess it will become clear when I try to use the lookup table in the decoder.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 23. Dezember 2021 09:31 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit  r572:   MDR16   is      some    kind    of      codebook.

Hi Gerd

I guessed that it was the \0 that cut the file off.

You mean something like answer 5 here:

https://stackoverflow.com/questions/759707/efficient-way-of-storing-huffman-...

I looked at this earlier trying to work out if it was relevant but didn't make it fit - I should have tried harder.

I still haven't spotted anything to determine the length of the 2 /3 byte in before and in the struct for {length}

Ticker

On Thu, 2021-12-23 at 01:17 +0000, Gerd Petermann wrote:

...

Hi Ticker,

sorry, just noticed that something went wrong with copy&paste because of the \0 character. Anyway, I think I understand the meaning of the part with the prefixes. I assume that Garmin reads the first 5 bits and uses this value as an index into a table which directly follows the first array. This 2nd table is a 32x2 lookup table, where the 2nd byte gives the value and the first byte some kind of status info which is used to position the bit reader. This would explain the repeating characters. Something like this:

--------- MDR 16 (decompression codebook Huffman tree) ------------ ---- --------- 000002b6 | 000000 | 4a                      | ???

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

Hi Ticker, a few more patterns: byte 4 seems to relate to the highest stat value in the rows with even stat values. I see e.g 0x0f and 0x1c or 0x0a and 0x1b. The formula: byte at 4 = highest /2 + 1 byte 6 (x) is related to the number of bytes (y) in the last block. (x = y * 2+ 1) I see e.g. 0x6b (107) and 53 bytes or 0x6d (109) with 54 bytes or 0x5d (93) and 46 bytes. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Donnerstag, 23. Dezember 2021 20:53 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Ticker, reg. "stat": my rule is a bit different but the result is the same: for all odd values: depth = usedBits = stat >> 1; val is the 2nd byte. for even stat values and rows where stat == val << 1 the decoder has to read exactly 1 more bit to decide which character was encoded. I've not yet understood how the stat or the val field can be used to find the correct entry in the byte array with the characters. So, maybe the stat value should be shifted to the right to make some sense. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 23. Dezember 2021 15:56 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd Maybe the "is always 8" is the character width. I think I understand parts of it. Read 5 bits and look up, giving 2 bytes. if first 3/5/6/9/b the final char in the second byte and return (b- first)/2 to the bit stream. Otherwise the combination somehow indicate a minimum number of more bits to read and where to start searching. maybe the 'struct for level' 1 or 2 bytes is a bit flag of which levels to look in. I notice (in topo_fr) it is normally a single or adjacent bits except for 0xa, but there are no chars at level 19 prefix 0 doesn't quite follow the rules Ticker On Thu, 2021-12-23 at 09:40 +0000, Gerd Petermann wrote:

Hi Ticker,

ouch, didn't even read that one :( Would have saved me a lot of time as my first idea was a "jump table". Attached is the new patch and the corrected mdr16 outputs produced with this patch.

So, besides the fields with ??? the only open question is the meaning of the struct bytes in the first table. I guess it will become clear when I try to use the lookup table in the decoder.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 23. Dezember 2021 09:31 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit r572: MDR16 is some kind of codebook.

Hi Gerd

I guessed that it was the \0 that cut the file off.

You mean something like answer 5 here:

https://stackoverflow.com/questions/759707/efficient-way-of-storing-huffman-...

I looked at this earlier trying to work out if it was relevant but didn't make it fit - I should have tried harder.

I still haven't spotted anything to determine the length of the 2 /3 byte in before and in the struct for {length}

Ticker

On Thu, 2021-12-23 at 01:17 +0000, Gerd Petermann wrote:

...

Hi Ticker,

sorry, just noticed that something went wrong with copy&paste because of the \0 character. Anyway, I think I understand the meaning of the part with the prefixes. I assume that Garmin reads the first 5 bits and uses this value as an index into a table which directly follows the first array. This 2nd table is a 32x2 lookup table, where the 2nd byte gives the value and the first byte some kind of status info which is used to position the bit reader. This would explain the repeating characters. Something like this:

--------- MDR 16 (decompression codebook Huffman tree) ------------ ---- --------- 000002b6 | 000000 | 4a | ???

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

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

Hi Ticker, attached patch implements also a table driven decoder for the adria topo map. The tree decoder and the table decode give the same values. I learned that I need this (hardcoded) array for Topo Adra int[] minCodes = {0,0,0,0,0,0,5,6,3,2,3,3,3,4,3,4,5,6,6,3,0}; I think these numbers are encoded in the struct bytes, but one has to shift the values. The shift amount is calculated by shift = maxDepth - depth. So, 06 00 00 | struct/mask for depth 19 ??? gives 6 >> (20-19) = 3 18 00 00 | struct/mask for depth 18 ??? gives 24 >> (20-18) = 4 ... 00 40 01 | struct/mask for depth 6 ??? gives 81920 >> (20 - 6) = 5 Found this last night, the patch doesn't implement this yet. I'll check your ideas about bytes 0..2. Those are the last which I don't understand. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 28. Dezember 2021 01:18 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd So, in the first byte of each prefix table entry, the bottom bit =1 means push 0-n bits back, =0 means need to get extra bits to decode. In both cases the value is >>1 and biased in a strange way. In most cases variable numbers of bits will be needed, but the minimum is known. Value of 0 means might need to get bits up to the max encoding length. Have you come up with a meaning for the second byte of the prefixes where it isn't a direct character. I see what you mean about byte 4. I don't follow what you mean about byte 6 and the length of the last block. Other static info that omight be encoded in bytes 0, 1 & 2 could be: 1/ version/subversion 2/ initial bits to read, giving size of prefix table (all 5 so far) 3/ includes refs to mdr29/30 &| 30/31. Which of your test maps have these sections? Ticker On Sun, 2021-12-26 at 19:39 +0000, Gerd Petermann wrote:

Hi Ticker,

a few more patterns: byte 4 seems to relate to the highest stat value in the rows with even stat values. I see e.g 0x0f and 0x1c or 0x0a and 0x1b. The formula: byte at 4 = highest /2 + 1

byte 6 (x) is related to the number of bytes (y) in the last block. (x = y * 2+ 1) I see e.g. 0x6b (107) and 53 bytes or 0x6d (109) with 54 bytes or 0x5d (93) and 46 bytes.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Donnerstag, 23. Dezember 2021 20:53 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit r572: MDR16 is some kind of codebook.

Hi Ticker,

reg. "stat": my rule is a bit different but the result is the same: for all odd values: depth = usedBits = stat >> 1;

val is the 2nd byte. for even stat values and rows where stat == val << 1 the decoder has to read exactly 1 more bit to decide which character was encoded. I've not yet understood how the stat or the val field can be used to find the correct entry in the byte array with the characters.

So, maybe the stat value should be shifted to the right to make some sense.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 23. Dezember 2021 15:56 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit r572: MDR16 is some kind of codebook.

Hi Gerd

Maybe the "is always 8" is the character width.

I think I understand parts of it.

Read 5 bits and look up, giving 2 bytes. if first 3/5/6/9/b the final char in the second byte and return (b- first)/2 to the bit stream. Otherwise the combination somehow indicate a minimum number of more bits to read and where to start searching. maybe the 'struct for level' 1 or 2 bytes is a bit flag of which levels to look in. I notice (in topo_fr) it is normally a single or adjacent bits except for 0xa, but there are no chars at level 19

prefix 0 doesn't quite follow the rules

Ticker

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

Hi Ticker, a few more findings for Adria Topo, Benelux and Topo Fr, probably true for all my maps: byte at 0: Any odd value lets MapSource crash Values 0x02, 0x06, 0x0a,0x0e, 0x12, ...., 0xfe all seem to work without any difference. Other even values produce either crashes or garbage in result lists. So it seems the two rightmost bits are flags, maybe reg. the algorithm that was used and any xxxx xx10 works. The byte at 1 seems to have no effect, I tried various values and found no change. Byte 2: all 0x?5 seem to work well. I did only change one of the three bytes at a time, maybe multiple changes would reveal more. I think I'll start coding support in mkgmap and we'll see what happens... Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Dienstag, 28. Dezember 2021 10:03 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Ticker, new patch seems to work with my 5 maps. reg. bytes 0..2 and 30/31 etc: The Adria Topo map has 30/31 and 32/33, the other 4 maps with MDR 16 don't have that. Info for some demo maps in gmapsupp format(they don't have 15/16) TransAlpin (2009) has 32/33, but not 30/31 TransAlpin (2012) has 30/31 and 32/33 Winter Activity Map has 30/31 and 32/33 2 (always 0x15 in my maps) may really be a bit flag and the 5 would be the table size. When I change it to 0x16 MapSource crashes, with 0x14 I see partly wrong strings. I found some code in GPXSee https://github.com/tumic0/GPXSee which handles huffman tables. I didn't try it yet but the program seems to be able to display GMP format, so maybe it'll help to understand that format. It didn't help me to understand the MDR16 so far and I don't think that exactly the same structure is used. Will keep on playing with those bytes to find out more... Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 28. Dezember 2021 01:18 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook. Hi Gerd So, in the first byte of each prefix table entry, the bottom bit =1 means push 0-n bits back, =0 means need to get extra bits to decode. In both cases the value is >>1 and biased in a strange way. In most cases variable numbers of bits will be needed, but the minimum is known. Value of 0 means might need to get bits up to the max encoding length. Have you come up with a meaning for the second byte of the prefixes where it isn't a direct character. I see what you mean about byte 4. I don't follow what you mean about byte 6 and the length of the last block. Other static info that omight be encoded in bytes 0, 1 & 2 could be: 1/ version/subversion 2/ initial bits to read, giving size of prefix table (all 5 so far) 3/ includes refs to mdr29/30 &| 30/31. Which of your test maps have these sections? Ticker On Sun, 2021-12-26 at 19:39 +0000, Gerd Petermann wrote:

Hi Ticker,

a few more patterns: byte 4 seems to relate to the highest stat value in the rows with even stat values. I see e.g 0x0f and 0x1c or 0x0a and 0x1b. The formula: byte at 4 = highest /2 + 1

byte 6 (x) is related to the number of bytes (y) in the last block. (x = y * 2+ 1) I see e.g. 0x6b (107) and 53 bytes or 0x6d (109) with 54 bytes or 0x5d (93) and 46 bytes.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Donnerstag, 23. Dezember 2021 20:53 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit r572: MDR16 is some kind of codebook.

Hi Ticker,

reg. "stat": my rule is a bit different but the result is the same: for all odd values: depth = usedBits = stat >> 1;

val is the 2nd byte. for even stat values and rows where stat == val << 1 the decoder has to read exactly 1 more bit to decide which character was encoded. I've not yet understood how the stat or the val field can be used to find the correct entry in the byte array with the characters.

So, maybe the stat value should be shifted to the right to make some sense.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 23. Dezember 2021 15:56 An: Development list for mkgmap Betreff: Re: [mkgmap-dev]       [mkgmap-svn]    Commit r572: MDR16 is some kind of codebook.

Hi Gerd

Maybe the "is always 8" is the character width.

I think I understand parts of it.

Read 5 bits and look up, giving 2 bytes. if first 3/5/6/9/b the final char in the second byte and return (b- first)/2 to the bit stream. Otherwise the combination somehow indicate a minimum number of more bits to read and where to start searching. maybe the 'struct for level' 1 or 2 bytes is a bit flag of which levels to look in. I notice (in topo_fr) it is normally a single or adjacent bits except for 0xa, but there are no chars at level 19

prefix 0 doesn't quite follow the rules

Ticker

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