[mkgmap-dev] [Patch v1] improve LinePreparer to reduce img size

Wed Jul 20 17:03:47 BST 2016

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 at lists.mkgmap.org.uk> im Auftrag von Alexandre de Menezes <afmlistas at 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:

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 at lists.mkgmap.org.uk><mailto:mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von nwillink <osm at pinns.co.uk><mailto:osm at pinns.co.uk>
Gesendet: Sonntag, 17. Juli 2016 16:59:19
An: mkgmap-dev at lists.mkgmap.org.uk<mailto:mkgmap-dev at 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-size-tp5878545p5878569.html
Sent from the Mkgmap Development mailing list archive at Nabble.com.
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk<mailto:mkgmap-dev at lists.mkgmap.org.uk>
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20160720/75c027e3/attachment-0001.html>