lua-users home
lua-l archive

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


Hi,

there seems to be a bug in the function 'countint' in 'ltable.c' of
version 'lua-5.2.0-alpha'.

It counts a key one off its correct position so that in border cases it
is counted in the wrong bucket. If a table is only populated by increasing
integer keys starting from 1, the hashtable should never be used. But the
erroneous counting would use it e.g. for a key '2^m+1', which does not fit
in the allocated array. This slows down performance, because a rehash has
to be done twice (for '2^m+1' and for '2^m+2').
In addition if  key = MAXASIZE = 2^MAXBITS is used, the non existent
bucket 'nums[MAXBITS+1]' is used with unpredictable results.

My suggestion:

static int countint (const TValue *key, int *nums) {
  int k = arrayindex(key);
  if (0 < k && k <= MAXASIZE) {  /* is `key' an appropriate array index? */
    /* nums[luaO_ceillog2(k)]++;  */ /* count as such */
    nums[luaO_ceillog2(k-1)]++  /* count as such [CORRECTING BUG] */
    return 1;
  }
  else
    return 0;
}

Regards,

Michael Rose
  

Schon gehört? WEB.DE hat einen genialen Phishing-Filter in die   
Toolbar eingebaut! http://produkte.web.de/go/toolbar