<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p>Hi Gerd,</p>
<p><br>
</p>
<p>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... ;)</p>
<p><br>
</p>
<p>But I see that you already pushed this fix, so kudos to you
(again!).</p>
<p><br>
</p>
<p>Best regards,</p>
<p><br>
</p>
<p> Alexandre<br>
</p>
<br>
<div class="moz-cite-prefix">On 20/07/2016 13:03, Gerd Petermann
wrote:<br>
</div>
<blockquote
cite="mid:HE1PR08MB0764EB9733E3D5405520C2B89E080@HE1PR08MB0764.eurprd08.prod.outlook.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
<div id="divtagdefaultwrapper"
style="font-size:12pt;color:#000000;background-color:#FFFFFF;font-family:Calibri,Arial,Helvetica,sans-serif;">
<p>Hi Alexandre,</p>
<p><br>
</p>
<p>in fact the img size is only reduced when the bit stream
length in bytes in shorter.<br>
</p>
<p>The new algo will prefer the trick, so if you are right and
the trick costs runtime</p>
<p>in the device I should change that. The effect is probably
very small though.<br>
</p>
<p><br>
</p>
<p>Gerd<br>
</p>
</div>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font style="font-size:11pt"
face="Calibri, sans-serif" color="#000000"><b>Von:</b>
mkgmap-dev <a class="moz-txt-link-rfc2396E" href="mailto:mkgmap-dev-bounces@lists.mkgmap.org.uk"><mkgmap-dev-bounces@lists.mkgmap.org.uk></a> im
Auftrag von Alexandre de Menezes
<a class="moz-txt-link-rfc2396E" href="mailto:afmlistas@terra.com.br"><afmlistas@terra.com.br></a><br>
<b>Gesendet:</b> Mittwoch, 20. Juli 2016 17:55:30<br>
<b>An:</b> Development list for mkgmap<br>
<b>Betreff:</b> Re: [mkgmap-dev] [Patch v1] improve
LinePreparer to reduce img size</font>
<div> </div>
</div>
<div>
<p>Hi Gerd,</p>
<p><br>
</p>
<p>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?<br>
</p>
<p><br>
</p>
<p>Does this make sense? Are you taking this into account when
choosing the best encoding?</p>
<p><br>
</p>
<p>Best regards,</p>
<p><br>
</p>
<p> Alexandre<br>
</p>
<br>
<div class="moz-cite-prefix">On 18/07/2016 04:22, Gerd Petermann
wrote:<br>
</div>
<blockquote
cite="mid:HE1PR08MB0764905B900B8C1464D2AFFB9E360@HE1PR08MB0764.eurprd08.prod.outlook.com"
type="cite">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
<div id="divtagdefaultwrapper" style="font-size:12pt;
color:#000000; background-color:#FFFFFF;
font-family:Calibri,Arial,Helvetica,sans-serif">
<p><br>
</p>
<meta content="text/html; charset=UTF-8">
<div dir="ltr">
<div id="x_divtagdefaultwrapper" style="font-size:12pt;
color:#000000; background-color:#FFFFFF;
font-family:Calibri,Arial,Helvetica,sans-serif">
<p>Let's try with a real world example:</p>
<p><a moz-do-not-send="true" id="LPlnk607062"
href="https://www.openstreetmap.org/way/245112355"
class="x_OWAAutoLink">https://www.openstreetmap.org/way/245112355</a></p>
<p><a moz-do-not-send="true" id="LPlnk607062"
href="https://www.openstreetmap.org/way/245112355"
class="x_OWAAutoLink"><br>
</a></p>
<p>This highway has 6 points, it starts in the north,
the x-delta values (in resolution 24) are
<br>
</p>
<p>4, -19, -5, 0, 3</p>
<p>The largest absolute value is 19 which requires 5
bits: 10011.</p>
<p>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)</p>
<p>So, the first iteration gives:</p>
<p>6 bit words : 4 = 000100 , -19 = 110011, -5 =
111011, 0 = 000000, 3 = 000011 --> 30 bits</p>
<p>Now, the optimization process starts trying to use
the "trick" with 5 bits. WIth the trick,</p>
<p>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)</p>
<p>All other values fit into 5 bits, so the 2nd
iteration gives:<br>
</p>
<p><span>5<span> bit words</span>: 4 = 00100 , -19 = <span>10000
11100</span>, -5 = 11011, 0 = 00000, 3 = 00011
--> 30 bits</span></p>
<p><span></span>The next step is to try with only 4
bits. Again, only the value -19 needs the trick, this
time we get - 19 = 1000
<span>1000 </span>1011 (7 +7 + 5 made negative)<br>
</p>
<p><span><span>4 bit words</span> : 4 = 0100 , -19 = <span>1000
1000 1011</span>, -5 = 1011, 0 = 0000, 3 = 0011
--> 24 bits</span></p>
<p><span></span></p>
<div>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
<span><span><span>100 100 100 100 100 100 111</span></span></span>
(3 + 3 + 3 + 3 + 3+ 3 + 1 made negative)<br>
The result:<br>
<p><span><span>3 bit words</span> : 4 = 100 001 , -19
= <span>100 100 100 100 100 100 111</span>, -5 =
100 110, 0 = 000, 3 = 011 --> 39 bits</span></p>
<p><span><br>
</span></p>
<p><span>So, we see that the trick is used too often
now and the resulting bit stream is much longer
than the one before.
<br>
</span></p>
<p><span><br>
</span></p>
<p><span>So, using the trick with 4 bit words saves 6
bits for the x values. <br>
</span></p>
<p><span><br>
</span></p>
<p><span>ciao,<br>
</span></p>
<p><span>Gerd<br>
</span></p>
</div>
P.S. To be complete:<br>
The y-deltas are all negative:<br>
-3, -7,- 3,- 5, -4<br>
This allows to encode only the absolute values which all
fit into 3 bits, the trick doesn't help here.<br>
<span></span><br>
</div>
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="x_divRplyFwdMsg" dir="ltr"><font
style="font-size:11pt" face="Calibri, sans-serif"
color="#000000"><b>Von:</b> mkgmap-dev
<a moz-do-not-send="true"
class="moz-txt-link-rfc2396E"
href="mailto:mkgmap-dev-bounces@lists.mkgmap.org.uk">
<mkgmap-dev-bounces@lists.mkgmap.org.uk></a>
im Auftrag von nwillink <a moz-do-not-send="true"
class="moz-txt-link-rfc2396E"
href="mailto:osm@pinns.co.uk">
<osm@pinns.co.uk></a><br>
<b>Gesendet:</b> Sonntag, 17. Juli 2016 16:59:19<br>
<b>An:</b> <a moz-do-not-send="true"
class="moz-txt-link-abbreviated"
href="mailto:mkgmap-dev@lists.mkgmap.org.uk">
mkgmap-dev@lists.mkgmap.org.uk</a><br>
<b>Betreff:</b> Re: [mkgmap-dev] [Patch v1] improve
LinePreparer to reduce img size</font>
<div> </div>
</div>
</div>
<font size="2"><span style="font-size:10pt">
<div class="PlainText">Many thanks for that Gerd<br>
<br>
I hope this makes it a bit clearer? <br>
<br>
The adjective 'crystal' does not immediately spring to
mind but I understand<br>
what<br>
you are getting at.<br>
<br>
Presumably the patch now checks every line for the
need to apply the trick.<br>
<br>
<br>
<br>
<br>
--<br>
View this message in context: <a
moz-do-not-send="true"
href="http://gis.19327.n5.nabble.com/Patch-v1-improve-LinePreparer-to-reduce-img-size-tp5878545p5878569.html">http://gis.19327.n5.nabble.com/Patch-v1-improve-LinePreparer-to-reduce-img-size-tp5878545p5878569.html</a><br>
Sent from the Mkgmap Development mailing list archive
at Nabble.com.<br>
_______________________________________________<br>
mkgmap-dev mailing list<br>
<a moz-do-not-send="true"
class="moz-txt-link-abbreviated"
href="mailto:mkgmap-dev@lists.mkgmap.org.uk">mkgmap-dev@lists.mkgmap.org.uk</a><br>
<a moz-do-not-send="true"
href="http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev">http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev</a><br>
</div>
</span></font></div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
mkgmap-dev mailing list
<a moz-do-not-send="true" class="moz-txt-link-abbreviated" href="mailto:mkgmap-dev@lists.mkgmap.org.uk">mkgmap-dev@lists.mkgmap.org.uk</a>
<a moz-do-not-send="true" class="moz-txt-link-freetext" href="http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev">http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev</a></pre>
</blockquote>
<br>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
mkgmap-dev mailing list
<a class="moz-txt-link-abbreviated" href="mailto:mkgmap-dev@lists.mkgmap.org.uk">mkgmap-dev@lists.mkgmap.org.uk</a>
<a class="moz-txt-link-freetext" href="http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev">http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev</a></pre>
</blockquote>
<br>
</body>
</html>