Re: [RFA] libiberty/hashtab.c, higher_prime_index: avoid array overrun

[Michael Snyder <msnyder@vmware.com>]

DJ Delorie wrote:
>> As written, the function will access element [30] of a 30-element array.
> 
> Um, no?
> 
>       unsigned int mid = low + (high - low) / 2;
> 
> This can never give mid == high unless low == high, which won't happen
> in that loop.
> 
> The math wants to search everything from (including) low to
> (excluding) high.
> 
> (but I'm willing to be proven wrong...)


Whee, here we go...


(gdb) b higher_prime_index
Breakpoint 2 at 0x79bed4: file 
/data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c, line 175.
(gdb) print higher_prime_index(0xffffffff)

Breakpoint 2, higher_prime_index (n=4294967295)
     at /data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c:175
175       unsigned int low = 0;
The program being debugged stopped while in a function called from GDB.
Evaluation of the expression containing the function
(higher_prime_index) will be abandoned.
When the function is done executing, GDB will silently stop.
(gdb) n
176       unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]) - 1;
(gdb)
178       while (low < high)
(gdb)
180           unsigned int mid = low + (high - low) / 2;
(gdb) display low
1: low = 0
(gdb) n
181           if (n > prime_tab[mid].prime)
1: low = 0
(gdb)
182             low = mid + 1;
1: low = 0(gdb) b higher_prime_index
Breakpoint 2 at 0x79bed4: file 
/data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c, line 175.
(gdb) print higher_prime_index(0xffffffff)

Breakpoint 2, higher_prime_index (n=4294967295)
     at /data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c:175
175       unsigned int low = 0;
The program being debugged stopped while in a function called from GDB.
Evaluation of the expression containing the function
(higher_prime_index) will be abandoned.
When the function is done executing, GDB will silently stop.
(gdb) n
176       unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]) - 1;
(gdb)
178       while (low < high)
(gdb)
180           unsigned int mid = low + (high - low) / 2;
(gdb) display low
1: low = 0
(gdb) n
181           if (n > prime_tab[mid].prime)
1: low = 0
(gdb)
182             low = mid + 1;
1: low = 0
(gdb)
178       while (low < high)
1: low = 16
(gdb)
180           unsigned int mid = low + (high - low) / 2;
1: low = 16
(gdb)
181           if (n > prime_tab[mid].prime)
1: low = 16
(gdb)
182             low = mid + 1;

(gdb)
178       while (low < high)
1: low = 16
(gdb)
180           unsigned int mid = low + (high - low) / 2;
1: low = 16
(gdb)
181           if (n > prime_tab[mid].prime)
1: low = 16
(gdb)
182             low = mid + 1;
1: low = 16
(gdb)
178       while (low < high)
1: low = 24
(gdb)
180           unsigned int mid = low + (high - low) / 2;
1: low = 24
(gdb)
181           if (n > prime_tab[mid].prime)
1: low = 24
(gdb)
182             low = mid + 1;
1: low = 24
(gdb)
178       while (low < high)
1: low = 28
(gdb)
180           unsigned int mid = low + (high - low) / 2;
1: low = 28
(gdb)
181           if (n > prime_tab[mid].prime)
1: low = 28
(gdb)
182             low = mid + 1;
1: low = 28
(gdb)
178       while (low < high)
1: low = 30
(gdb)
188       if (n > prime_tab[low].prime)
1: low = 30
(gdb)