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

[Michael Snyder <msnyder at vmware dot com>]

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.




#include <stdio.h>
#include <stdlib.h>

typedef unsigned int hashval_t;

struct prime_ent
{
  hashval_t prime;
  hashval_t inv;
  hashval_t inv_m2;     /* inverse of prime-2 */
  hashval_t shift;
};

static struct prime_ent const prime_tab[] = {
  {          7, 0x24924925, 0x9999999b, 2 },
  {         13, 0x3b13b13c, 0x745d1747, 3 },
  {         31, 0x08421085, 0x1a7b9612, 4 },
  {         61, 0x0c9714fc, 0x15b1e5f8, 5 },
  {        127, 0x02040811, 0x0624dd30, 6 },
  {        251, 0x05197f7e, 0x073260a5, 7 },
  {        509, 0x01824366, 0x02864fc8, 8 },
  {       1021, 0x00c0906d, 0x014191f7, 9 },
  {       2039, 0x0121456f, 0x0161e69e, 10 },
  {       4093, 0x00300902, 0x00501908, 11 },
  {       8191, 0x00080041, 0x00180241, 12 },
  {      16381, 0x000c0091, 0x00140191, 13 },
  {      32749, 0x002605a5, 0x002a06e6, 14 },
  {      65521, 0x000f00e2, 0x00110122, 15 },
  {     131071, 0x00008001, 0x00018003, 16 },
  {     262139, 0x00014002, 0x0001c004, 17 },
  {     524287, 0x00002001, 0x00006001, 18 },
  {    1048573, 0x00003001, 0x00005001, 19 },
  {    2097143, 0x00004801, 0x00005801, 20 },
  {    4194301, 0x00000c01, 0x00001401, 21 },
  {    8388593, 0x00001e01, 0x00002201, 22 },
  {   16777213, 0x00000301, 0x00000501, 23 },
  {   33554393, 0x00001381, 0x00001481, 24 },
  {   67108859, 0x00000141, 0x000001c1, 25 },
  {  134217689, 0x000004e1, 0x00000521, 26 },
  {  268435399, 0x00000391, 0x000003b1, 27 },
  {  536870909, 0x00000019, 0x00000029, 28 },
  { 1073741789, 0x0000008d, 0x00000095, 29 },
  { 2147483647, 0x00000003, 0x00000007, 30 },
  /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
  { 0xfffffffb, 0x00000006, 0x00000008, 31 }
};

static unsigned int
higher_prime_index (unsigned long n)
{
  unsigned int low = 0;
  unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);

  while (low != high)
    {
      unsigned int mid = low + (high - low) / 2;
      if (n > prime_tab[mid].prime)
        low = mid + 1;
      else
        high = mid;
    }

  /* If we've run out of primes, abort.  */
  if (n > prime_tab[low].prime)
    {
      fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
      abort ();
    }

  return low;
}


int
main (int argc, char **argv)
{
  if (argc < 2)
    {
      fprintf (stderr, "Usage: hash <number>\n");
      return 1;
    }

  printf ("Answer: %d\n", higher_prime_index (strtoul (argv[1], NULL, 0)));
  return 0;
}