Hi all, Attached is 2nd version of the patch. The improvements are a bit better, although I've removed one change in PolygonSplitterBase which reduces the number of splits in rare cases (e.g. when the map contains large sea areas). I think this change is okay, but it is not related to the LinePreparer and thus should be handled separately. A new binary containing the attached patch(es) is here: http://files.mkgmap.org.uk/download/302/mkgmap.jar If I here no complains I'll commit both patch next wednesday. Gerd ________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Alexandre Loss <alexandre.loss@gmail.com> Gesendet: Samstag, 16. Juli 2016 19:43:23 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] [Patch v1] improve LinePreparer to reduce img size Great discovery Gerd! Enviado do meu iPhone Em 16 de jul de 2016, ?s 14:28, Gerd Petermann <GPetermann_muenchen@hotmail.com<mailto:GPetermann_muenchen@hotmail.com>> escreveu: Hi all, during the last days I tried to find more about the way how mkgmap stores polygons, esp. why we have some limits. While doing that I stumbled over an old comment in LinePreparer.java: // I don't care about getting the smallest possible file size so // err on the side of caution. which made me curious because I do care ;-) I found out that Garmin offers a "trick" in the delta encoding which allows to reduce the needed bytes in some cases, the imgformat-1.0.pdf explains this in detail, search for " only the sign bit is set ". This "trick" helps esp. well when coastline polygons or rivers are stored. I can explain this more detailed if somebody likes to know more, for now I'd like to hear if the trick causes any problems, I did not find any so far. A binary with this and a slightly improved overview_levels_v2.patch can be found here: http://files.mkgmap.org.uk/download/301/mkgmap.jar Depending on the data a single tile with size ~5MB may be reduced by 50 - 500+kB. Gerd <reduceImgSize_v1.patch> _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk<mailto:mkgmap-dev@lists.mkgmap.org.uk> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Nick, nwillink wrote

As a matter of interest how long does a delta need to be for it to be treated as a special case?

This depends on the number of bits which are used. The typical case with a coastline polygon is that we have a lot of very small delta values and one or two large values for the straight lines. The unpatched algo uses these large values to calculate the needed number of bits (e.g. 8), the patch implements an iterative search which decreases the number of bits and tries if the resulting bit stream is shorter. Each value that cannot be represented with e.g. 7 bits needs the trick. If only one value is stored with the trick, and we have to store 50 values, we have 50 * 8 = 400 bits with the old and 49 * 7 + 1 * (7+7) = 357 bits for the trick. So, the iteration would continue with 6 bits, maybe 5 bits and so on until too many values are encoded with the trick (or the the large values are encoeded with too many bits) and the bit stream length increases again. I hope this makes it a bit clearer? Gerd -- View this message in context: http://gis.19327.n5.nabble.com/Patch-v1-improve-LinePreparer-to-reduce-img-s... Sent from the Mkgmap Development mailing list archive at Nabble.com.

Let's try with a real world example: https://www.openstreetmap.org/way/245112355 <https://www.openstreetmap.org/way/245112355> This highway has 6 points, it starts in the north, the x-delta values (in resolution 24) are 4, -19, -5, 0, 3 The largest absolute value is 19 which requires 5 bits: 10011. Since both positive and negative values exist, we have to encode the sign for each single delta value, so we have to use 6 bits (the leftmost gives the sign) So, the first iteration gives: 6 bit words : 4 = 000100 , -19 = 110011, -5 = 111011, 0 = 000000, 3 = 000011 --> 30 bits Now, the optimization process starts trying to use the "trick" with 5 bits. WIth the trick, the value 19 doesn't fit into 5 bits, so the trick is used (it stands for the binary value 1111) and the result for -19 is 10000 11100 (15 + 4 made negative) All other values fit into 5 bits, so the 2nd iteration gives: 5 bit words: 4 = 00100 , -19 = 10000 11100, -5 = 11011, 0 = 00000, 3 = 00011 --> 30 bits The next step is to try with only 4 bits. Again, only the value -19 needs the trick, this time we get - 19 = 1000 1000 1011 (7 +7 + 5 made negative) 4 bit words : 4 = 0100 , -19 = 1000 1000 1011, -5 = 1011, 0 = 0000, 3 = 0011 --> 24 bits The next step is to try with only 3 bits. This time, more values need the trick (4 , -5 and -19). For -19 we get 100 100 100 100 100 100 111 (3 + 3 + 3 + 3 + 3+ 3 + 1 made negative) The result: 3 bit words : 4 = 100 001 , -19 = 100 100 100 100 100 100 111, -5 = 100 110, 0 = 000, 3 = 011 --> 39 bits So, we see that the trick is used too often now and the resulting bit stream is much longer than the one before. So, using the trick with 4 bit words saves 6 bits for the x values. ciao, Gerd P.S. To be complete: The y-deltas are all negative: -3, -7,- 3,- 5, -4 This allows to encode only the absolute values which all fit into 3 bits, the trick doesn't help here. ________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von nwillink <osm@pinns.co.uk> Gesendet: Sonntag, 17. Juli 2016 16:59:19 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] [Patch v1] improve LinePreparer to reduce img size Many thanks for that Gerd I hope this makes it a bit clearer? The adjective 'crystal' does not immediately spring to mind but I understand what you are getting at. Presumably the patch now checks every line for the need to apply the trick. -- View this message in context: http://gis.19327.n5.nabble.com/Patch-v1-improve-LinePreparer-to-reduce-img-s... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Nick, thanks for the motivation reg. "producing a supplement". In fact I thought about this quite often, but whenever I start to document such details I feel very unsure about the format and the needed simplification. I agree that the availabledocumentation (including wiki and other sources) is behind the current knowledge represented by the code in mkgmap. On the other hand, I do like to answer specific questions, because I can expect that the reader really wants to know the details. So, I don't see myself as an author, but I'd be happy to deliver answers. Gerd ________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von nwillink <osm@pinns.co.uk> Gesendet: Montag, 18. Juli 2016 10:50:47 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] [Patch v1] improve LinePreparer to reduce img size Hi Gerd Many thanks for this brilliant and indeed crystal clear explanation! I now understand when the trick is no longer feasible. Ever considered producing a supplement to Mechalas' great achievement?I'm sure there is a great demand for it. Will now do some testing. Thanks again Nick -- View this message in context: http://gis.19327.n5.nabble.com/Patch-v1-improve-LinePreparer-to-reduce-img-s... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Andrzej, I did not find a simple way to predict the bit stream length without repeating lots of code lines. On the other hand, I also did not see an effect on the run time, so the simple iteration looked good enough to me. If you find different results, I'll try again. In the meantime I was working on other improvements in the existing filters, found some more special cases which can be improved, but the effect will probably be smaller. Gerd ________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Andrzej Popowski <popej@poczta.onet.pl> Gesendet: Dienstag, 19. Juli 2016 13:09:15 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] [Patch v1] improve LinePreparer to reduce img size Hi Gerd, this is great improvement, thanks! I have tested your patch on a road map and get about 4% decrease of map size. I'm compiling topo map now, I think it is over 10% size reduction. I would like to suggest some optimizing of code. I think, you can get optimum bit length directly in procedure calcDeltas from LinePreparer. Just instead of only looking for min/max bit length, create full profile: number of legs vs bit length, so you can estimate full bit size like you have done it in your previous posts, without actually processing a line. I hope this makes sens, I don't know your code so well. -- Best regards, Andrzej _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Gerd, I am not familiar with the format, but from your explanation I am guessing this will be at some point stored in full bytes (or words or dwords). Assuming bytes, there will be indeed a size gain going from 30bits to 24bits as in your example, but not in going from 32 to 26, for example. In this case, wouldn't the original encoding be simpler (faster) to decode? Does this make sense? Are you taking this into account when choosing the best encoding? Best regards, Alexandre On 18/07/2016 04:22, Gerd Petermann wrote:

Let's try with a real world example:

https://www.openstreetmap.org/way/245112355

<https://www.openstreetmap.org/way/245112355>

This highway has 6 points, it starts in the north, the x-delta values (in resolution 24) are

4, -19, -5, 0, 3

The largest absolute value is 19 which requires 5 bits: 10011.

Since both positive and negative values exist, we have to encode the sign for each single delta value, so we have to use 6 bits (the leftmost gives the sign)

So, the first iteration gives:

6 bit words : 4 = 000100 , -19 = 110011, -5 = 111011, 0 = 000000, 3 = 000011 --> 30 bits

Now, the optimization process starts trying to use the "trick" with 5 bits. WIth the trick,

the value 19 doesn't fit into 5 bits, so the trick is used (it stands for the binary value 1111) and the result for -19 is 10000 11100 (15 + 4 made negative)

All other values fit into 5 bits, so the 2nd iteration gives:

5bit words: 4 = 00100 , -19 = 10000 11100, -5 = 11011, 0 = 00000, 3 = 00011 --> 30 bits

The next step is to try with only 4 bits. Again, only the value -19 needs the trick, this time we get - 19 = 1000 1000 1011 (7 +7 + 5 made negative)

4 bit words : 4 = 0100 , -19 = 1000 1000 1011, -5 = 1011, 0 = 0000, 3 = 0011 --> 24 bits

The next step is to try with only 3 bits. This time, more values need the trick (4 , -5 and -19). For -19 we get 100 100 100 100 100 100 111 (3 + 3 + 3 + 3 + 3+ 3 + 1 made negative) The result:

3 bit words : 4 = 100 001 , -19 = 100 100 100 100 100 100 111, -5 = 100 110, 0 = 000, 3 = 011 --> 39 bits

So, we see that the trick is used too often now and the resulting bit stream is much longer than the one before.

So, using the trick with 4 bit words saves 6 bits for the x values.

ciao,

Gerd

P.S. To be complete: The y-deltas are all negative: -3, -7,- 3,- 5, -4 This allows to encode only the absolute values which all fit into 3 bits, the trick doesn't help here.

------------------------------------------------------------------------ *Von:* mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von nwillink <osm@pinns.co.uk> *Gesendet:* Sonntag, 17. Juli 2016 16:59:19 *An:* mkgmap-dev@lists.mkgmap.org.uk *Betreff:* Re: [mkgmap-dev] [Patch v1] improve LinePreparer to reduce img size Many thanks for that Gerd

I hope this makes it a bit clearer?

The adjective 'crystal' does not immediately spring to mind but I understand what you are getting at.

Presumably the patch now checks every line for the need to apply the trick.

-- View this message in context: http://gis.19327.n5.nabble.com/Patch-v1-improve-LinePreparer-to-reduce-img-s... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

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

Hi Gerd, I agree. The speed improvement, if existent, should be very small. But if you multiply that by the thousands in each map, and multiply by the number of time the map is loaded, and multiply by the number of map users, the gain should be worth it. Besides that, I always strive for the better solution... ;) But I see that you already pushed this fix, so kudos to you (again!). Best regards, Alexandre On 20/07/2016 13:03, Gerd Petermann wrote:

Hi Alexandre,

in fact the img size is only reduced when the bit stream length in bytes in shorter.

The new algo will prefer the trick, so if you are right and the trick costs runtime

in the device I should change that. The effect is probably very small though.

Gerd

------------------------------------------------------------------------ *Von:* mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Alexandre de Menezes <afmlistas@terra.com.br> *Gesendet:* Mittwoch, 20. Juli 2016 17:55:30 *An:* Development list for mkgmap *Betreff:* Re: [mkgmap-dev] [Patch v1] improve LinePreparer to reduce img size

Hi Gerd,

I am not familiar with the format, but from your explanation I am guessing this will be at some point stored in full bytes (or words or dwords). Assuming bytes, there will be indeed a size gain going from 30bits to 24bits as in your example, but not in going from 32 to 26, for example. In this case, wouldn't the original encoding be simpler (faster) to decode?

Does this make sense? Are you taking this into account when choosing the best encoding?

Best regards,

Alexandre

On 18/07/2016 04:22, Gerd Petermann wrote:

...

Let's try with a real world example:

https://www.openstreetmap.org/way/245112355

<https://www.openstreetmap.org/way/245112355>

This highway has 6 points, it starts in the north, the x-delta values (in resolution 24) are

4, -19, -5, 0, 3

The largest absolute value is 19 which requires 5 bits: 10011.

Since both positive and negative values exist, we have to encode the sign for each single delta value, so we have to use 6 bits (the leftmost gives the sign)

So, the first iteration gives:

6 bit words : 4 = 000100 , -19 = 110011, -5 = 111011, 0 = 000000, 3 = 000011 --> 30 bits

Now, the optimization process starts trying to use the "trick" with 5 bits. WIth the trick,

the value 19 doesn't fit into 5 bits, so the trick is used (it stands for the binary value 1111) and the result for -19 is 10000 11100 (15 + 4 made negative)

All other values fit into 5 bits, so the 2nd iteration gives:

5bit words: 4 = 00100 , -19 = 10000 11100, -5 = 11011, 0 = 00000, 3 = 00011 --> 30 bits

The next step is to try with only 4 bits. Again, only the value -19 needs the trick, this time we get - 19 = 1000 1000 1011 (7 +7 + 5 made negative)

4 bit words : 4 = 0100 , -19 = 1000 1000 1011, -5 = 1011, 0 = 0000, 3 = 0011 --> 24 bits

The next step is to try with only 3 bits. This time, more values need the trick (4 , -5 and -19). For -19 we get 100 100 100 100 100 100 111 (3 + 3 + 3 + 3 + 3+ 3 + 1 made negative) The result:

3 bit words : 4 = 100 001 , -19 = 100 100 100 100 100 100 111, -5 = 100 110, 0 = 000, 3 = 011 --> 39 bits

So, we see that the trick is used too often now and the resulting bit stream is much longer than the one before.

So, using the trick with 4 bit words saves 6 bits for the x values.

ciao,

Gerd

P.S. To be complete: The y-deltas are all negative: -3, -7,- 3,- 5, -4 This allows to encode only the absolute values which all fit into 3 bits, the trick doesn't help here.

------------------------------------------------------------------------ *Von:* mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von nwillink <osm@pinns.co.uk> *Gesendet:* Sonntag, 17. Juli 2016 16:59:19 *An:* mkgmap-dev@lists.mkgmap.org.uk *Betreff:* Re: [mkgmap-dev] [Patch v1] improve LinePreparer to reduce img size Many thanks for that Gerd

I hope this makes it a bit clearer?

The adjective 'crystal' does not immediately spring to mind but I understand what you are getting at.

Presumably the patch now checks every line for the need to apply the trick.

-- View this message in context: http://gis.19327.n5.nabble.com/Patch-v1-improve-LinePreparer-to-reduce-img-s... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

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

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

Hi Jakob, the trick is used whenever it saves bytes. It is more likely that this happens when you have many nodes, it is not related to the type of line. Gerd Jakob Mühldorfer-2 wrote

Hi Gerd,

is this trick only good for polygons or does this work with normal streets/tracks as well?

Jakob

Am 16.07.2016 um 19:28 schrieb Gerd Petermann:

...

Hi all,

during the last days I tried to find more about the way how mkgmap stores

polygons, esp. why we have some limits. While doing that I stumbled over an

old comment in LinePreparer.java:

// I don't care about getting the smallest possible file size so // err on the side of caution.

which made me curious because I do care ;-)

I found out that Garmin offers a "trick" in the delta encoding which allows

to reduce the needed bytes in some cases, the imgformat-1.0.pdf

explains this in detail, search for " only the sign bit is set ".

This "trick" helps esp. well when coastline polygons or rivers are stored.

I can explain this more detailed if somebody likes to know more,

for now I'd like to hear if the trick causes any problems, I did not find any

so far.

A binary with this and a slightly improved overview_levels_v2.patch

can be found here:

http://files.mkgmap.org.uk/download/301/mkgmap.jar

Depending on the data a single tile with size ~5MB may be reduced by 50 - 500+kB.

Gerd

_______________________________________________ mkgmap-dev mailing list

mkgmap-dev@.org

...

http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list

mkgmap-dev@.org

http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-- View this message in context: http://gis.19327.n5.nabble.com/Patch-v1-improve-LinePreparer-to-reduce-img-s... Sent from the Mkgmap Development mailing list archive at Nabble.com.