lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index] 

On Mon, May 02, 2011 at 11:50:14AM +0200, Michael Rose wrote:
> <html><head></head><body bgcolor='#FFFFFF' style='font-size:12px;background-color:#FFFFFF;font-family:Verdana, Arial, sans-serif;'>Hi,<br/><br/>there seems to be a bug in the function 'countint' in 'ltable.c' of<br/>version 'lua-5.2.0-alpha'.<br/><br/>It counts a key one off its correct position so that in border cases it<br/>is counted in the wrong bucket. If a table is only populated by increasing<br/>integer keys starting from 1, the hashtable should never be used. But the<br/>erroneous counting would use it e.g. for a key '2^m+1', which does not fit<br/>in the allocated array. This slows down performance, because a rehash has<br/>to be done twice (for '2^m+1' and for '2^m+2').<br/>In addition if&nbsp; key = MAXASIZE = 2^MAXBITS is used, the non existent<br/>bucket 'nums[MAXBITS+1]' is used with unpredictable results.<br/><br/>My suggestion:<br/><br/>static int countint (const TValue *key, int *nums) {<br/>&nbsp; int k = arrayindex(key);<br/>&nbsp; if (0 &lt; k &amp;&amp; k &lt;= MAXASIZE) {&nbsp; /* is `key' an appropriate array index? */<br/>&nbsp;&nbsp;&nbsp; /* nums[luaO_ceillog2(k)]++;&nbsp; */ /* count as such */<br/>&nbsp;&nbsp;&nbsp; nums[luaO_ceillog2(k-1)]++&nbsp; /* count as such [CORRECTING BUG] */<br/>&nbsp;&nbsp;&nbsp; return 1;<br/>&nbsp; }<br/>&nbsp; else<br/>&nbsp;&nbsp;&nbsp; return 0;<br/>}<br/><br/>Regards,<br/><br/>Michael Rose<br/>&nbsp;&nbsp;<br><br><table cellpadding="0" cellspacing="0" border="0"><tr><td bgcolor="#000000"><img src="https://img.ui-portal.de/p.gif"; width="1" height="1" border="0" alt="" /></td></tr><tr><td style="font-family:verdana; font-size:12px; line-height:17px;">Schon geh&ouml;rt? WEB.DE hat einen genialen Phishing-Filter in die&nbsp;&nbsp;&nbsp;<br>Toolbar eingebaut! <a href="http://produkte.web.de/go/toolbar";><b>http://produkte.web.de/go/toolbar</b></a></td></tr></table>
> </body></html>

You'll have a much better chance of somebody reading and replying to you
if you send plain text emails, or at least emails that contain both
plain text and HTML (and even that is frowned upon here.)

B.