[mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
From Gerd Petermann gpetermann_muenchen at hotmail.com on Sat Dec 18 10:19:34 GMT 2021
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 at lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen at 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 at lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap at 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 at 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 at lists.mkgmap.org.uk> im Auftrag > von Ticker Berkin <rwb-mkgmap at 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/assign6/warmup > > https://stackoverflow.com/questions/759707/efficient-way-of-storing-huffman-tree > > > > Gerd > > > _______________________________________________ > mkgmap-dev mailing list > 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 _______________________________________________ mkgmap-dev mailing list 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
- Previous message: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
- Next message: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the mkgmap-dev mailing list