Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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 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 im Auftrag von Gerd Petermann Gesendet: Dienstag, 28. Dezember 2021 10:03 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kindof 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 im Auftrag von Ticker Berkin Gesendet: Dienstag, 28. Dezember 2021 01:18 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kindof 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 +, 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 im Auftrag > von Gerd Petermann > Gesendet: Donnerstag, 23. Dezember 2021 20:53 > An: Development list for mkgmap > Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: > MDR16 is somekindof 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 im Auftrag > von Ticker Berkin > Gesendet: Donnerstag, 23. Dezember 2021 15:56 > An: Development list for mkgmap > Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: > MDR16 is somekindof 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
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 im Auftrag von Ticker Berkin Gesendet: Dienstag, 28. Dezember 2021 01:18 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kindof 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 +, 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 im Auftrag > von Gerd Petermann > Gesendet: Donnerstag, 23. Dezember 2021 20:53 > An: Development list for mkgmap > Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: > MDR16 is somekindof 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 im Auftrag > von Ticker Berkin > Gesendet: Donnerstag, 23. Dezember 2021 15:56 > An: Development list for mkgmap > Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: > MDR16 is somekindof 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 mdr-experimental-table_v1b.patch Description: mdr-experimental-table_v1b.patch ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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 im Auftrag von Ticker
Berkin
Gesendet: Dienstag, 28. Dezember 2021 01:18
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some
kindof 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 +, 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 im Auftrag
> von Gerd Petermann
> Gesendet: Donnerstag, 23. Dezember 2021 20:53
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572:
> MDR16 is somekindof 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 im Auftrag
> von Ticker Berkin
> Gesendet: Donnerstag, 23. Dezember 2021 15:56
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572:
> MDR16 is somekindof 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
mdr-experimental-table_beta.patch
Description: mdr-experimental-table_beta.patch
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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 +, 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 im Auftrag > von Gerd Petermann > 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 im Auftrag > von Ticker Berkin > 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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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 im Auftrag von Gerd
Petermann
Gesendet: Donnerstag, 23. Dezember 2021 20:53
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is
somekindof 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 im Auftrag von Ticker
Berkin
Gesendet: Donnerstag, 23. Dezember 2021 15:56
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is
somekindof 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 +, 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 im Auftrag
> von Ticker Berkin
> Gesendet: Donnerstag, 23. Dezember 2021 09:31
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572:
> MDR16 is somekindof 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-tree
>
>
> 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 +, Gerd Petermann wrote:
> > Hi Ticker,
> >
> > sorry, just noticed that something went wrong with copy
> > 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)
> >
> > -
> > 02b6 | 00 | 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
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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 im Auftrag von Ticker
Berkin
Gesendet: Donnerstag, 23. Dezember 2021 15:56
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is
somekindof 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 +, 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 im Auftrag
> von Ticker Berkin
> Gesendet: Donnerstag, 23. Dezember 2021 09:31
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572:
> MDR16 is somekindof 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-tree
>
>
> 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 +, Gerd Petermann wrote:
> > Hi Ticker,
> >
> > sorry, just noticed that something went wrong with copy
> > 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)
> >
> > -
> > 02b6 | 00 | 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
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 +, 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 im Auftrag
> von Ticker Berkin
> 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-tree
>
>
> 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 +, Gerd Petermann wrote:
> > Hi Ticker,
> >
> > sorry, just noticed that something went wrong with copy
> > 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)
> >
> > -
> > 02b6 | 00 | 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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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 im Auftrag von Ticker
Berkin
Gesendet: Donnerstag, 23. Dezember 2021 09:31
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is
somekind 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-tree
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 +, Gerd Petermann wrote:
> Hi Ticker,
>
> sorry, just noticed that something went wrong with copy 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)
> -
> 02b6 | 00 | 4a | ???
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mdr-experimental-v2.patch
Description: mdr-experimental-v2.patch
- MDR 16 (decompression codebook Huffman tree) -
030e | 00 | 8e | ???
030f | 01 | 02 | ???
0310 | 02 | 15 | ???
0311 | 03 | 10 | 1st level with struct: 16
0312 | 04 | 0a 08 6d| ??? (2nd byte always 8?)
0315 | 07 | 00 00 | struct for 16
0317 | 09 | 10 | level: 16
0318 | 0a | 00 | count byte 0, delta = 0
0319 | 0b | 06 00 | struct for 16
031b | 0d | 0f | level: 15
031c | 0e | 06 | count byte 6, delta = 6
031d | 0f | 14 00 | struct for 15
031f | 11 | 0e | level: 14
0320 | 12 | 0d | count byte 13, delta = 7
0321 | 13 | 38 00 | struct for 14
0323 | 15 | 0d | level: 13
0324 | 16 | 16 | count byte 22, delta = 9
0325 | 17 | 70 00 | struct for 13
0327 | 19 | 0c | level: 12
0328 | 1a | 1d | count byte 29, delta = 7
0329 | 1b | a0 00 | struct for 12
032b | 1d | 0b | level: 11
032c | 1e | 20 | count byte 32, delta = 3
032d | 1f | 00 01 | struct for 11
032f | 21 | 09 | level: 9
0330 | 22 | 23 | count byte 35, delta = 3
0331 | 23 | 00 02 | struct for 9
0333 | 25 | 08 | level: 8
0334 | 26 | 25 | count byte 37, delta = 2
0335 | 27 | 00 04 | struct for 8
0337 | 29 | 07 | level: 7
0338 | 2a | 27 | count byte 39, delta = 2
0339 | 2b | 00 0c | struct for 7
033b | 2d | 06 | level: 6
033c | 2e | 2b | count byte 43, delta = 4
|| |
lookup table
033d | 2f | 00 08 | prefix 0 : stat=0 v='.', 0x8
033f | 31 | 10 09 | prefix 1 : stat=16 v='.', 0x9
0341 | 33 | 12 09 | prefix 00010 : stat=18 v='.', 0x9
0343 | 35 | 12 09 | prefix 00011 : stat=18 v='.', 0x9
0345 | 37 | 12 09 | prefix 00100 : stat=18 v='.', 0x9
0347 | 39 | 12 09 | prefix 00101 : stat=18 v='.', 0x9
0349 | 3b | 12 09 | p
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-tree
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 +, Gerd Petermann wrote:
> Hi Ticker,
>
> sorry, just noticed that something went wrong with copy 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)
> -
> 02b6 | 00 | 4a | ???
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
v='.', 0x0 0326 | 70 | 09 00 | prefix 0 : stat=9 v='.', 0x0 0328 | 72 | 09 20 | prefix 1 : stat=9 v=' ', 0x20 032a | 74 | 09 20 | prefix 10001 : stat=9 v=' ', 0x20 032c | 76 | 09 45 | prefix 10010 : stat=9 v='E', 0x45 032e | 78 | 09 45 | prefix 10011 : stat=9 v='E', 0x45 0330 | 7a | 09 4e | prefix 10100 : stat=9 v='N', 0x4e 0332 | 7c | 09 4e | prefix 10101 : stat=9 v='N', 0x4e 0334 | 7e | 09 4f | prefix 10110 : stat=9 v='O', 0x4f 0336 | 80 | 09 4f | prefix 10111 : stat=9 v='O', 0x4f 0338 | 82 | 09 49 | prefix 11000 : stat=9 v='I', 0x49 033a | 84 | 09 49 | prefix 11001 : stat=9 v='I', 0x49 033c | 86 | 09 52 | prefix 11010 : stat=9 v='R', 0x52 033e | 88 | 09 52 | prefix 11011 : stat=9 v='R', 0x52 0340 | 8a | 07 41 | prefix 11100 : stat=7 v='A', 0x41 0342 | 8c | 07 41 | prefix 11101 : stat=7 v='A', 0x41 0344 | 8e | 07 41 | prefix 0 : stat=7 v='A', 0x41 0346 | 90 | 07 41 | prefix 1 : stat=7 v='A', 0x41 Obviously, for the prefixes 0..00100 the decode has to read more bits to find the position in the rest of the mdr16 section... stat=7 means 3 bits where processed, stat=9 means 4 bits where processed, stat=11 means 5 bits where processed. Have to double check this... Gerd Von: mkgmap-dev im Auftrag von Gerd Petermann Gesendet: Mittwoch, 22. Dezember 2021 15:22 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is somekindof codebook. Hi Ticker, I think those are the two that I didn't post before. Gerd Von: mkgmap-dev im Auftrag von Ticker Berkin Gesendet: Mittwoch, 22. Dezember 2021 12:32 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is somekindof 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 +, 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 ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
Hi Ticker, I think those are the two that I didn't post before. Gerd Von: mkgmap-dev im Auftrag von Ticker Berkin Gesendet: Mittwoch, 22. Dezember 2021 12:32 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is somekindof 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 +, 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 - MDR 16 (decompression codebook Huffman tree) - 030e | 00 | 8e | ??? 030f | 01 | 02 | ??? 0310 | 02 | 15 | ??? 0311 | 03 | 10 | 1st level with struct: 16 0312 | 04 | 0a 08 6d 00 00 | ??? 0317 | 09 | 10 | struct level: 16 0318 | 0a | 00 | count byte 0, delta = 0 0319 | 0b | 06 00 | struct for 16 031b | 0d | 0f | struct level: 15 031c | 0e | 06 | count byte 6, delta = 6 031d | 0f | 14 00 | struct for 15 031f | 11 | 0e | struct level: 14 0320 | 12 | 0d | count byte 13, delta = 7 0321 | 13 | 38 00 | struct for 14 0323 | 15 | 0d | struct level: 13 0324 | 16 | 16 | count byte 22, delta = 9 0325 | 17 | 70 00 | struct for 13 0327 | 19 | 0c | struct level: 12 0328 | 1a | 1d | count byte 29, delta = 7 0329 | 1b | a0 00 | struct for 12 032b | 1d | 0b | struct level: 11 032c | 1e | 20 | count byte 32, delta = 3 032d | 1f | 00 01 | struct for 11 032f | 21 | 09 | struct level: 9 0330 | 22 | 23 | count byte 35, delta = 3 0331 | 23 | 00 02 | struct for 9 0333 | 25 | 08 | struct level: 8 0334 | 26 | 25 | count byte 37, delta = 2 0335 | 27 | 00 04 | struct for 8 0337 | 29 | 07 | struct level: 7 0338 | 2a | 27 | count byte 39, delta = 2 0339 | 2b | 00 0c | struct for 7 033b | 2d | 06 | struct level: 6 033c | 2e | 2b | count byte 43, delta = 4 033d | 2f | 00 08 | struct for 6 033f | 31 | 10 09 12 09 12 09 12 09 | ??? 0347 | 39 | 12 09 12 09 | 034b | 3d | 0b | prefix b 034c | 3e | 59 | value in tree 'Y' (0x59) 034d | 3f | 0b | prefix b 034e | 40 | 47 | value in tree 'G' (0x47) 034f | 41 | 0b | prefix b 0350 | 42 | 49 | value in tree 'I' (0x49) 0351 | 43 | 0b | prefix b 0352 | 44 | c1 | value in tree 'Ã' (0xc1) 0353 | 45 | 0b | prefix b 0354 | 46 | 5a | value in tree 'Z' (0x5a) 0355 | 47 | 0b | prefix b 0356 | 48 | 4b | value in tree 'K' (0x4b) 0357 | 49 | 0b | prefix b 0358 | 4a | 44 | value in tree 'D' (0x44) 0359 | 4b | 0b | prefix b 035a | 4c | 4f | value in tree 'O' (0x4f) 035b | 4d | 0b | prefix b 035c | 4e | 4e | value in tree 'N' (0x4e) 035d | 4f | 09 | prefix 9 035e | 50 | 54 | value in tree 'T' (0x54) 035f | 51 | 09 | prefix 9 0360 | 52 | 54 | value in tree 'T' (0x54) 0361 | 53 | 09
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 +, 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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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 im Auftrag von Gerd
Petermann
Gesendet: Dienstag, 21. Dezember 2021 17:49
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is
somekind 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 im Auftrag von Gerd
Petermann
Gesendet: Montag, 20. Dezember 2021 11:29
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is
somekind 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("
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
Hi Gerd That's great. I don't have any maps with compression/Mdr16 or Mdr30-3. http://gis.19327.n8.nabble.com no longer seems to work for me. I found possible links to maps at: http://www.garniak.pl/viewtopic.php?f=9=398 but interesting links were dead or went to generic page. I suspect the #bytes after the delta for each level might be related to the size of Mdr15 or some bits in byte 0/4/5/6 and related to letter frequency count. I didn't notice a different length sequence (6 or 5) starting at byte 4 in the mdr sections you sent (benelix, topo_d_v3 and the original) I puzzled over the values before the level 5 data and couldn't see a way of working out how many there were and what they might mean. The benelux map is confusing because it is 0b 16 0b 16 0b. It is going to be interesting when re-generating this to find out how much of all the unknown or redundant information is required by the Garmin software! Ticker On Tue, 2021-12-21 at 16:49 +, Gerd Petermann wrote: > 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 ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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 im Auftrag von Gerd
Petermann
Gesendet: Montag, 20. Dezember 2021 11:29
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is
somekindof 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("110", 'H');
addHuffmanNode("111", '1');
addHuffmanNode("0001000", '2');
addHuffmanNode("0001001", '.');
// depth 8
addHuffmanNode("0011", '5');
addHuffmanNode("0100", '6');
addHuffmanNode("0101", '-');
addHuffmanNode("0110", '7');
addHuffmanNode("0111", '3');
addHuffmanNode("1000", '8');
addHuffmanNode("1001", '9');
addHuffmanNode("1010", '0');
addHuffmanNode("1011", '4');
// depth 9
addHuffmanNode("00010", 'F');
addHuffmanNode("00011",',');
addHuffmanNode("00100", '(');
addHuffmanNode("00101", ')');
// depth 10
addHuffmanNode("11", '*');
// depth 11
addHuffmanNode("011", 'Y');
addHuffmanNode("100", '"');
addHuffmanNode("101", (char) 0x06); //
non-print4
// depth 12
addHuffmanNode("0011", 'W');
addHuffmanNode("0100", 'X');
addHuffmanNode("0101", (char) 0x05);
//non-print some shield code
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
epth 16
addHuffmanNode("0101", (char)
0x04); // non-print3
addHuffmanNode("0110", '!');
addHuffmanNode("0111", (char)
0x9e); //Ž
// depth 17
addHuffmanNode("00110",'+');
addHuffmanNode("00111", '–'); //
different to minus mdr16: 0x96
addHuffmanNode("01000", 'Á'); //Á
addHuffmanNode("01001", 'Ü');
// depth 18
addHuffmanNode("000110", '_');
addHuffmanNode("000111", '{');
addHuffmanNode("001000", '“'); //
mdr16: 0x93
addHuffmanNode("001001", 'É');
addHuffmanNode("001010", 'Ð');
addHuffmanNode("001011", 'Ö');
// depth 19
addHuffmanNode("011", '?');
addHuffmanNode("100", '`'); //
mdr16: 0x60
addHuffmanNode("101", '„'); //
mdr16: 0x84
addHuffmanNode("110", 'ž'); //
mdr16: 0x8e
addHuffmanNode("111", '’'); //
mdr16: 0x92
addHuffmanNode("0001000", 'Ä');
addHuffmanNode("0001001", 'Ø');
addHuffmanNode("0001010", 'Ú');
addHuffmanNode("0001011", 'Û');
// depth 20
addHuffmanNode("", '#'); //
offset into MDR 30/31? MapSource displays "HWY "
addHuffmanNode("0001", '%'); //
addHuffmanNode("0010", ':');
addHuffmanNode("0011", ';');
addHuffmanNode("0100", (char)
0x8f);
addHuffmanNode("00000101", (char)
0xb8);
Gerd
Von: mkgmap-dev im Auftrag von Gerd
Petermann
Gesendet: Montag, 20. Dezember 2021 10:59
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is
somekindof 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 im Auftrag von Ticker
Berkin
Gesendet: Montag, 20. Dezember 2021 10:38
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is
somekindof 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:
02cf | 000019 | 11 | struct level: 17
02d0 | 1a | 15 50 00 00 | struct for 17
02d4 | 1e | 10 | struct level: 16
02d5 | 1f | 19 80 00 00 | struct for 16
02d9 | 23 | 0f | struct level: 15
02da | 24 | 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 +, Gerd Petermann wrote:
> Hi Ticker,
> please explain. What counters do you see? What do they mean?
>
> Gerd
>
>
> Von: mkgmap-dev im Auftrag von
> Ticker Berkin
> Gesendet: Montag, 20. Dezember 2021 09:49
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16
> is somekindof codebook.
>
>
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 im Auftrag von Ticker
Berkin
Gesendet: Montag, 20. Dezember 2021 10:38
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is
somekindof 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:
02cf | 19 | 11 | struct level: 17
02d0 | 1a | 15 50 00 00 | struct for 17
02d4 | 1e | 10 | struct level: 16
02d5 | 1f | 19 80 00 00 | struct for 16
02d9 | 23 | 0f | struct level: 15
02da | 24 | 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 +, Gerd Petermann wrote:
> Hi Ticker,
> please explain. What counters do you see? What do they mean?
>
> Gerd
>
>
> Von: mkgmap-dev im Auftrag von
> Ticker Berkin
> Gesendet: Montag, 20. Dezember 2021 09:49
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16
> is somekindof 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 +, 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 im Auftrag
> > von Ticker Berkin
> > Gesendet: Sonntag, 19. Dezember 2021 10:12
> > An: Development list for mkgmap
> > Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572:
> > MDR16 is somekindof 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 #06 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
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:
02cf | 19 | 11 | struct level: 17
02d0 | 1a | 15 50 00 00 | struct for 17
02d4 | 1e | 10 | struct level: 16
02d5 | 1f | 19 80 00 00 | struct for 16
02d9 | 23 | 0f | struct level: 15
02da | 24 | 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 +, Gerd Petermann wrote:
> Hi Ticker,
> please explain. What counters do you see? What do they mean?
>
> Gerd
>
>
> Von: mkgmap-dev im Auftrag von
> Ticker Berkin
> 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 +, 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 im Auftrag
> > von Ticker Berkin
> > 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 #06 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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
Hi Ticker,
please explain. What counters do you see? What do they mean?
Gerd
Von: mkgmap-dev im Auftrag von Ticker
Berkin
Gesendet: Montag, 20. Dezember 2021 09:49
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is
somekindof 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 +, 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 im Auftrag
> von Ticker Berkin
> Gesendet: Sonntag, 19. Dezember 2021 10:12
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572:
> MDR16 is somekindof 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 #06 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
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 +, 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 im Auftrag
> von Ticker Berkin
> 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 #06 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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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 im Auftrag von Ticker
Berkin
Gesendet: Sonntag, 19. Dezember 2021 10:12
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is
somekindof 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 #06 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
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 #06 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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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 im Auftrag von Ticker Berkin Gesendet: Samstag, 18. Dezember 2021 11:52 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is somekindof 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 +, 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 ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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 +, 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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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 im Auftrag von Gerd Petermann Gesendet: Freitag, 17. Dezember 2021 09:20 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is somekind 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) - 02b6 | 00 | 4a | ??? 02b7 | 01 | 03 | bytes for struct: 3 + 1 = 4 02b8 | 02 | 15 | ??? 02b9 | 03 | 14 | 1st level with struct: 20 02ba | 04 | 0f 08 85 00 00 00 | ??? 02c0 | 0a | 14 | struct level: 20 02c1 | 0b | 00 06 00 00 | struct for 20 02c5 | 0f | 13 | struct level: 19 02c6 | 10 | 06 18 00 00 | struct for 19 02ca | 14 | 12 | struct level: 18 02cb | 15 | 0f 30 00 00 | struct for 18 02cf | 19 | 11 | struct level: 17 02d0 | 1a | 15 50 00 00 | struct for 17 02d4 | 1e | 10 | struct level: 16 02d5 | 1f | 19 80 00 00 | struct for 16 02d9 | 23 | 0f | struct level: 15 02da | 24 | 1c c0 00 00 | struct for 15 02de | 28 | 0e | struct level: 14 02df | 29 | 1e 00 02 00 | struct for 14 02e3 | 2d | 0d | struct level: 13 02e4 | 2e | 23 00 03 00 | struct for 13 02e8 | 32 | 0c | struct level: 12 02e9 | 33 | 25 00 06 00 | struct for 12 02ed | 37 | 0b | struct level: 11 02ee | 38 | 28 00 0c 00 | struct for 11 02f2 | 3c | 0a | struct level: 10 02f3 | 3d | 2b 00 10 00 | struct for 10 02f7 | 41 | 09 | struct level: 9 02f8 | 42 | 2c 00 30 00 | struct for 9 02fc | 46 | 08 | struct level: 8 02fd | 47 | 30 00 c0 00 | struct for 8 0301 | 4b | 07 | struct level: 7 0302 | 4c | 39 00 40 01 | struct for 7 0306 | 50 | 06 | struct level: 6 0307 | 51 | 3d 00 0c 18 | struct for 6 smaller tree (TopoGuide Hungary with codepage 1250): 030e | 00 | 8e | ??? 030f | 01 | 02 | bytes for struct: 2 + 1 = 3 0310 | 02 | 15 | ??? 0311 | 03 | 10 | 1st level with struct: 16 0312 | 04 | 0a 08 6d 00 00 | ??? 0317 | 09 | 10 | struct level: 16 0318 | 0a | 00 06 00| struct for 16 031b | 0d | 0f | struct level: 15 031c | 0e | 06 14 00| struct for 15 031f | 11 | 0e | struct level: 14 0320 | 12 | 0d 38 00| struct for 14 0323 | 15 | 0d | struct level: 13 0324 | 16 | 16 70 00| struct for 13 0327 | 19 | 0c | struct level: 12 0328 | 1a | 1d a0 00| struct for 12 032b | 1d | 0b | struct level: 11 032c | 1e | 20 00 01| struct for 11 032f | 21 | 09 | struct level: 9 0330 | 22 | 23 00 02| struct for 9 0333 | 25 | 08 | struct level: 8 0334 | 26 | 25 00 04| struct for 8 0337 | 29 | 07 | struct level: 7 0338 | 2a | 27 00 0c| struct for 7 033b | 2d | 06 | struct level: 6 033c | 2e
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
| 60 | 4c 09 4c 09 52 09 52 07 | L.L.R.R. 0376 | 68 | 00 07 00 07 00 07 00 33 | ...3 037e | 70 | 34 37 9d c5 de 32 36 38 | 47ÅÞ268 0386 | 78 | 51 ad c2 ce 27 31 5f 28 | QÂÎ'1_( 038e | 80 | aa c4 29 cf d0 57 9e ba | ªÄ)ÏÐWº 0396 | 88 | c3 c6 d2 dd 58 be 2c 8a | ÃÆÒÝX¾, 039e | 90 | c8 2e cd db da dc 4a 20 | È.ÍÛÚÜJ 03a6 | 98 | 46 2d 42 43 50 c9 55 4d | F-BCPÉUM 03ae | a0 | d3 d5 d6 48 56 | ÓÕÖHV Gerd Von: mkgmap-dev im Auftrag von Ticker Berkin Gesendet: Donnerstag, 16. Dezember 2021 18:33 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is somekindof 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 +, 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 > Gesendet: Donnerstag, 16. Dezember 2021 15:42 > An: Development list for mkgmap > Betreff: AW: [mkgmap-dev] [mkgmap-svn] Commit r572: > MDR16 is somekindof 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 im Auftrag > von Ticker Berkin > Gesendet: Donnerstag, 16. Dezember 2021 10:04 > An: Development list for mkgmap > Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: > MDR16 is somekindof 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 +, 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@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
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 +, 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 > 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 im Auftrag > von Ticker Berkin > 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 +, 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@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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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 Gesendet: Donnerstag, 16. Dezember 2021 15:42 An: Development list for mkgmap Betreff: AW: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is somekindof 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 im Auftrag von Ticker Berkin Gesendet: Donnerstag, 16. Dezember 2021 10:04 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is somekindof 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 +, 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@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev - MDR 16 (decompression codebook Huffman tree) - || | Unknown 177 bytes: 02ae | 00 | be 02 15 12 0c 08 5d 00 | ¾.]. 02b6 | 08 | 00 00 12 00 06 00 00 11 | 02be | 10 | 06 0c 00 00 10 09 20 00 | .. . 02c6 | 18 | 00 0f 0e 50 00 00 0e 14 | ...P 02ce | 20 | e0 00 00 0d 1d 00 01 00 | à... 02d6 | 28 | 0c 1e 80 01 00 0b 20 00 | ..?... . 02de | 30 | 03 00 0a 23 00 04 00 08 | ...# 02e6 | 38 | 24 00 08 00 07 25 00 20 | $%. 02ee | 40 | 00 06 28 00 0a 16 0b 16 | ..(. 02f6 | 48 | 0b 16 0b 0b 55 0b 44 0b | U.D. 02fe | 50 | 48 0b 4b 0b 20 0b 47 09 | H.K. .G. 0306 | 58 | 4e 09 4e 09 4c 09 4c 09 | N.N.L.L. 030e | 60 | 41 09 41 09 53 09 53 09 | A.A.S.S. 0316 | 68 | 49 09 49 09 52 09 52 09 | I.I.R.R. 031e | 70 | 4f 09 4f 09 00 09 00 09 | O.O. 0326 | 78 | 54 09 54 07 45 07 45 07 | T.T.E.E. 032e | 80 | 45 07 45 22 30 39 3c 60 | E.E"09<` 0336 | 88 | c7 3e cf d4 34 35 36 37 | Ç>ÏÔ4567 033e | 90 | c0 32 38 33 c4 ca db 2c | À283ÄÊÛ, 0346 | 98 | 28 31 c2 2f 29 2e d6 dc | (1Â/).ÖÜ 034e | a0 | c8 51 cb 58 27 c9 59 46 | ÈQËX'ÉYF 0356 | a8 | 5a 4a 2d 56 57 50 42 43 | ZJ-VWPBC 035e | b0 | 4d | M - MDR 16 (decompression codebook Huffman tree) - || | Unknown 210 bytes: 02a6 | 00 | 42 03 15 16 10 08 77 00 | B.w. 02ae | 08 | 00 00 16 00 06 00 00 15 | 02b6 | 10 | 06 18 00 00 14 0f 20 00 | .. . 02be | 18 | 00 13 11 30 00 00 12 13 | ...0 02c6 | 20 | 60 00 00 11 16 80 00 00 | `?.. 02ce | 28 | 0f 17 00 01 00 0e 18 00 | 02d6 | 30 | 02 00 0d 19 00 04 00 0c | 02de | 38 | 1a 00 18 00 0b 1f 00 20 | ... 02e6 | 40 | 00 0a 20 00 80 00 09 26 | .. .?..& 02ee | 48 | 00 80 01 08 2e 00 80 02 | .??. 02f6 | 50 | 07 32 00 00 04 06 35 00 | .25. 02fe | 58 | 0d 1a 0e 1e 0f 1e 0f 1e | 0306 | 60 | 0f 0b 42 0b 4c 0b 4f 0b | ..B.L.O. 030e | 68 | 4d 0b 55 0b 49 0b 47 09 | M.U.I.G. 0316 | 70 | 53 09 53 09 52 09 52 09 | S.S.R.R. 031e | 78 | 48 09 48 09 4e 09 4e 09 | H.H.N.N. 0326 | 80 | 20 09 20 09 54 09 54 09 | . .T.T. 032e | 88 | 00 09 00 09 41 09 41 07 | A.A. 0336 | 90 | 45 07 45 07 45 07 45 9f | E.E.E.E? 033e | 98 | b0 cf d2 d9 db 60 c2 ca | °ÏÒÙÛ`ÂÊ 0
Re: [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 im Auftrag von Ticker Berkin Gesendet: Donnerstag, 16. Dezember 2021 10:04 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is somekindof 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 +, 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@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
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 +, 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@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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
Von: mkgmap-dev im Auftrag von Ticker
Berkin
Gesendet: Mittwoch, 15. Dezember 2021 19:26
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is
somekindof 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 00s, 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 00{fixedLenInxNotZero}
Ticker
On Wed, 2021-12-15 at 17:35 +, 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 im Auftrag
> von Gerd Petermann
> Gesendet: Mittwoch, 15. Dezember 2021 13:07
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572:
> MDR16 is somekindof 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
> "".
> 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
> ""
> 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 im Auftrag
> von Ticker Berkin
> Gesendet: Mittwoch, 15. Dezember 2021 12:47
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16
> is somekindof 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 +, 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
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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 00s, 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 00{fixedLenInxNotZero}
Ticker
On Wed, 2021-12-15 at 17:35 +, 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 im Auftrag
> von Gerd Petermann
> 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
> "".
> 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
> ""
> 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 im Auftrag
> von Ticker Berkin
> 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 +, 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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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 im Auftrag von Gerd Petermann Gesendet: Mittwoch, 15. Dezember 2021 13:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn]Commit r572: MDR16 is somekindof 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 "". 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 "" 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 im Auftrag von Ticker Berkin Gesendet: Mittwoch, 15. Dezember 2021 12:47 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kindof 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 +, 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
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 "". 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 "" 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 im Auftrag von Ticker Berkin Gesendet: Mittwoch, 15. Dezember 2021 12:47 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kindof 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 +, 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
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 +, 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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
111", '–'); //
different to minus
addHuffNode("00110",'+');
addHuffNode("001011", 'Ö');
addHuffNode("001010", 'Ð');
addHuffNode("001001", 'É');
addHuffNode("001000", '“');
addHuffNode("000111", '{');
addHuffNode("000110", '_');
addHuffNode("0001011", 'Û');
addHuffNode("0001010", 'Ú');
addHuffNode("0001001", 'Ø');
addHuffNode("0001000", 'Ä');
addHuffNode("111", '’');
addHuffNode("000000000000110", 'ž');
addHuffNode("101", '„');
addHuffNode("100", '`');
addHuffNode("01", '¸'); //
special comma
addHuffNode("001", ';');
addHuffNode("0001", '%'); //
addHuffNode("", '#'); //
offset into MDR 30/31? MapSource displays HWY
Gerd
Von: mkgmap-dev im Auftrag von Gerd
Petermann
Gesendet: Dienstag, 14. Dezember 2021 19:42
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some
kindof codebook.
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 im Auftrag von Ticker
Berkin
Gesendet: Dienstag, 14. Dezember 2021 19:30
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some
kindof 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 +, 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("000", 'F');
> add("110", 'H');
> add("111", '1');
> add("0001001", '.');
>
> add("0011", '5');
> add("0100", '6');
> add("0111", '7');
> add("1000", '8');
> add("1001", '9');
> add("1010", '0');
> add("1011", '4');
> add("0101", '-');
> add("00100", '(');
> add("00101", ')');
>
> 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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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 im Auftrag von Ticker
Berkin
Gesendet: Dienstag, 14. Dezember 2021 19:30
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some
kindof 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 +, 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("000", 'F');
> add("110", 'H');
> add("111", '1');
> add("0001001", '.');
>
> add("0011", '5');
> add("0100", '6');
> add("0111", '7');
> add("1000", '8');
> add("1001", '9');
> add("1010", '0');
> add("1011", '4');
> add("0101", '-');
> add("00100", '(');
> add("00101", ')');
>
> 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
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 +, 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("000", 'F');
> add("110", 'H');
> add("111", '1');
> add("0001001", '.');
>
> add("0011", '5');
> add("0100", '6');
> add("0111", '7');
> add("1000", '8');
> add("1001", '9');
> add("1010", '0');
> add("1011", '4');
> add("0101", '-');
> add("00100", '(');
> add("00101", ')');
>
> Gerd
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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("000", 'F');
add("110", 'H');
add("111", '1');
add("0001001", '.');
add("0011", '5');
add("0100", '6');
add("0111", '7');
add("1000", '8');
add("1001", '9');
add("1010", '0');
add("1011", '4');
add("00000101", '-');
add("00100", '(');
add("00101", ')');
Gerd
Von: mkgmap-dev im Auftrag von Ticker
Berkin
Gesendet: Dienstag, 14. Dezember 2021 18:09
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some
kindof 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
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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 im Auftrag von Ticker Berkin 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 001000. 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 +, 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' > 1010 -> '0' > 0100 -> '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 111 -> 'A' 0111 -> '\0' 1010 -> 'N' 1011 -> 'O' 1100 -> 'I' 1101 -> 'R' 00101 -> 'C' 00110 -> 'S' 01000 -> 'T' 01001 -> 'M' 01010 -> 'V' 111 -> '1' 0001001 -> '.' 1010 -> '0' 0100 -> '6' 0111 -> '7' 1000 -> '8' 1011 -> '4' 1010 -> '7' 1001 -> '9' 0011 -> '5' UL ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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 001000. 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 +, 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' > 1010 -> '0' > 0100 -> '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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
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' 1010 -> '0' 0100 -> '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 im Auftrag von Ticker Berkin 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 +, Gerd Petermann wrote: > Hi Ticker, > > maybe you need this? > --Analyse sections that are known-- > MDR 17 len=0 next= > implied size=0 (0x0) > MDR 18 len=0 next= > implied size=0 (0x0) > MDR 19 len=0 next= > implied size=694 (0x2b6) > MDR 16 02b6 len=d4 next=038a > fixed record size 212 > number of records 1,00 > implied size=1697585 (0x19e731) +++MISMATCH > size multiplier 8007,48 8007 > MDR 1 0019e9e7 len=138next=0019eb1f > fixed record size 12 > number of records 26,00 > implied size=312 (0x138) > > Gerd > > > Von: mkgmap-dev im Auftrag > von Ticker Berkin > 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 +, Gerd Petermann wrote: > > Hi Ticker, > > > > not sure what you mean. Here is the output from MdrDisplay: > > 00df | 3f 23 51 00 | MDR 15 at offset 0x51233f > > 00e3 | d5 b3 0f 00 | MDR 15 length 1029077 > > | | End of section 0060d714, len > > 0x0fb3d5 > > 00e7 | 01 | String flag 1 > > | | > > 00e8 | b6 02 00 00 | MDR 16 at offset 0x0002b6 > > 00ec | d4 00 00 00 | MDR 16 length 212 > > | | End of section 038a, len > > 0xd4 > > 00f0 | d4 00 | MDR 16 record size d4 > > | | Number of records 1 > > 00f2 | 00 00 00 00 | MDR 16 header flags > > | | > > > > Gerd > > > > ________ > > Von: mkgmap-dev im Auftrag > > von Ticker Berkin > > Gesendet: Montag, 13. Dezember 2021 13:34 > > An: mkgmap-dev@lists.mkgmap.org.uk; mkgmap-...@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 +, 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=572 > > > ___ > > > mkgmap-svn mailing list > > > To unsubscribe send an mail to > > > mkgmap-svn-le...@lists.mkgmap.org.uk > > &
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 +, Gerd Petermann wrote: > Hi Ticker, > > maybe you need this? > --Analyse sections that are known-- > MDR 17 len=0 next= > implied size=0 (0x0) > MDR 18 len=0 next= > implied size=0 (0x0) > MDR 19 len=0 next= > implied size=694 (0x2b6) > MDR 16 02b6 len=d4 next=038a > 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 im Auftrag > von Ticker Berkin > 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 +, Gerd Petermann wrote: > > Hi Ticker, > > > > not sure what you mean. Here is the output from MdrDisplay: > > 00df | 3f 23 51 00 | MDR 15 at offset 0x51233f > > 00e3 | d5 b3 0f 00 | MDR 15 length 1029077 > > | | End of section 0060d714, len > > 0x0fb3d5 > > 00e7 | 01 | String flag 1 > > | | > > 00e8 | b6 02 00 00 | MDR 16 at offset 0x0002b6 > > 00ec | d4 00 00 00 | MDR 16 length 212 > > | | End of section 038a, len > > 0xd4 > > 00f0 | d4 00 | MDR 16 record size d4 > > | | Number of records 1 > > 00f2 | 00 00 00 00 | MDR 16 header flags > > | | > > > > Gerd > > > > ____________ > > Von: mkgmap-dev im Auftrag > > von Ticker Berkin > > Gesendet: Montag, 13. Dezember 2021 13:34 > > An: mkgmap-dev@lists.mkgmap.org.uk; mkgmap-...@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 +, 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=572 > > > ___ > > > mkgmap-svn mailing list > > > To unsubscribe send an mail to > > > mkgmap-svn-le...@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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
Hi Ticker, maybe you need this? --Analyse sections that are known-- MDR 17 len=0 next= implied size=0 (0x0) MDR 18 len=0 next= implied size=0 (0x0) MDR 19 len=0 next= implied size=694 (0x2b6) MDR 16 02b6 len=d4 next=038a fixed record size 212 number of records 1,00 implied size=1697585 (0x19e731) +++MISMATCH size multiplier 8007,48 8007 MDR 1 0019e9e7 len=138next=0019eb1f fixed record size 12 number of records 26,00 implied size=312 (0x138) Gerd Von: mkgmap-dev im Auftrag von Ticker Berkin 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 +, Gerd Petermann wrote: > Hi Ticker, > > not sure what you mean. Here is the output from MdrDisplay: > 00df | 3f 23 51 00 | MDR 15 at offset 0x51233f > 00e3 | d5 b3 0f 00 | MDR 15 length 1029077 > | | End of section 0060d714, len > 0x0fb3d5 > 00e7 | 01 | String flag 1 > | | > 00e8 | b6 02 00 00 | MDR 16 at offset 0x0002b6 > 00ec | d4 00 00 00 | MDR 16 length 212 > | | End of section 038a, len > 0xd4 > 00f0 | d4 00 | MDR 16 record size d4 > | | Number of records 1 > 00f2 | 00 00 00 00 | MDR 16 header flags > | | > > Gerd > > > Von: mkgmap-dev im Auftrag > von Ticker Berkin > Gesendet: Montag, 13. Dezember 2021 13:34 > An: mkgmap-dev@lists.mkgmap.org.uk; mkgmap-...@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 +, 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=572 > > ___ > > mkgmap-svn mailing list > > To unsubscribe send an mail to mkgmap-svn-le...@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
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 +, Gerd Petermann wrote: > Hi Ticker, > > not sure what you mean. Here is the output from MdrDisplay: > 00df | 3f 23 51 00 | MDR 15 at offset 0x51233f > 00e3 | d5 b3 0f 00 | MDR 15 length 1029077 > | | End of section 0060d714, len > 0x0fb3d5 > 00e7 | 01 | String flag 1 > | | > 00e8 | b6 02 00 00 | MDR 16 at offset 0x0002b6 > 00ec | d4 00 00 00 | MDR 16 length 212 > | | End of section 038a, len > 0xd4 > 00f0 | d4 00 | MDR 16 record size d4 > | | Number of records 1 > 00f2 | 00 00 00 00 | MDR 16 header flags > | | > > Gerd > > > Von: mkgmap-dev im Auftrag > von Ticker Berkin > Gesendet: Montag, 13. Dezember 2021 13:34 > An: mkgmap-dev@lists.mkgmap.org.uk; mkgmap-...@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 +, 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=572 > > ___ > > mkgmap-svn mailing list > > To unsubscribe send an mail to mkgmap-svn-le...@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
Re: [mkgmap-dev] [mkgmap-svn] Commit r572: MDR16 is some kind of codebook.
Hi Ticker, not sure what you mean. Here is the output from MdrDisplay: 00df | 3f 23 51 00 | MDR 15 at offset 0x51233f 00e3 | d5 b3 0f 00 | MDR 15 length 1029077 | | End of section 0060d714, len 0x0fb3d5 00e7 | 01 | String flag 1 | | 00e8 | b6 02 00 00 | MDR 16 at offset 0x0002b6 00ec | d4 00 00 00 | MDR 16 length 212 | | End of section 038a, len 0xd4 00f0 | d4 00 | MDR 16 record size d4 | | Number of records 1 00f2 | 00 00 00 00 | MDR 16 header flags | | Gerd Von: mkgmap-dev im Auftrag von Ticker Berkin Gesendet: Montag, 13. Dezember 2021 13:34 An: mkgmap-dev@lists.mkgmap.org.uk; mkgmap-...@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 +, 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=572 > ___ > mkgmap-svn mailing list > To unsubscribe send an mail to mkgmap-svn-le...@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
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 +, 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=572 > ___ > mkgmap-svn mailing list > To unsubscribe send an mail to mkgmap-svn-le...@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
