| Message ID | 4D701056.1080208@vmware.com |
|---|---|
| State | New |
| Headers | show |
> 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...)
DJ Delorie wrote: >> As written, the function will access element [30] of a 30-element array. > > Um, no? Y-uh-huh! > 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...) I am willing to do that! ;-) Compile this program, run it under gdb with the input "0xffffffff", and step through the code. You will see it assign the value "30" to "low" and use it to access the array. I suppose you could do it directly just by loading gdb into gdb, putting a breakpoint at the above function, and then calling it from gdb with the input 0xffffffff.
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)
Bizzare, the problem isn't the hash loop, it's the error handler at the end! It never uses [30] for the main loop, only if you give it a number between 0xfffffffb and 0xffffffff - and in the case where it would use [30], it's supposed to abort anyway. I couldn't figure out why your patch worked until I realized that the main loop still fails! It works because the error handler just doesn't abort, returning the last array entry, which happens to be the right one. I think a suitable comment explaining what's actually going on, and why it still works, is warranted... but your patch is OK with me otherwise :-)
On Mar 3, 2011, at 2:26 PM, Michael Snyder wrote: > DJ Delorie wrote: >>> As written, the function will access element [30] of a 30-element array. >> Um, no? > > Y-uh-huh! fight fight fight... :-) There can be only one.
Mike Stump wrote: > On Mar 3, 2011, at 2:26 PM, Michael Snyder wrote: >> DJ Delorie wrote: >>>> As written, the function will access element [30] of a 30-element array. >>> Um, no? >> Y-uh-huh! > > fight fight fight... :-) There can be only one. Oh, did I forget the smiley? ;-)
On 03/03/2011 23:00, Mike Stump wrote: > On Mar 3, 2011, at 2:26 PM, Michael Snyder wrote: >> DJ Delorie wrote: >>>> As written, the function will access element [30] of a 30-element array. >>> Um, no? >> Y-uh-huh! > > fight fight fight... :-) There can be only one. I was just wondering whether now would be a good time to mention that having prime-sized hash tables is only a workaround against the danger of someone providing an inadequate hash function implementation in the first place? cheers, DaveK
> I was just wondering whether now would be a good time to mention
Probably not, gcc being in stage 4 and all...
DJ Delorie wrote: > Bizzare, the problem isn't the hash loop, it's the error handler at > the end! It never uses [30] for the main loop, only if you give it a > number between 0xfffffffb and 0xffffffff - and in the case where it > would use [30], it's supposed to abort anyway. > > I couldn't figure out why your patch worked until I realized that the > main loop still fails! It works because the error handler just > doesn't abort, returning the last array entry, which happens to be the > right one. > > I think a suitable comment explaining what's actually going on, and > why it still works, is warranted... but your patch is OK with me > otherwise :-) Please give me the comment, and I'll check it in.
Index: hashtab.c =================================================================== RCS file: /cvs/src/src/libiberty/hashtab.c,v retrieving revision 1.38 diff -u -p -u -p -r1.38 hashtab.c --- hashtab.c 3 Feb 2011 07:23:59 -0000 1.38 +++ hashtab.c 3 Mar 2011 22:01:08 -0000 @@ -173,9 +173,9 @@ static unsigned int higher_prime_index (unsigned long n) { unsigned int low = 0; - unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]); + unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]) - 1; - while (low != high) + while (low < high) { unsigned int mid = low + (high - low) / 2; if (n > prime_tab[mid].prime)