Re: optimization/5344 gcc 3.0.3 optimizer generates incorrect code

[Ricardo Anguiano <anguiano at codesourcery dot com>]

Greetings,

This email is a response to GNATS submission #5344.  I do not have
access to change the GNATS database.

Running the C code by hand reveals the binary search algorithm
implementation to be incorrect: It doesn't handle the following case
well:
        array of size 1
	containing fd=34
	searching for fd=40

The variable *p_i ends up the the value of 2.

The main problem with this code is that the variable tmp1 is unsigned.
The Writer assumes temp1 can be negative.  Sections of code dealing
with temp1 < 0 are optimized away they are not possible.  If diff is
used instead, the generated code is different, because diff is signed
and therefore can be negative.

This code reveals no bugs in the compiler.  Please don't make compiler
maintainers debug your code.  Use a standard library function like
bsearch.

A paraphrase from \emph{Programming Pearls}, second edition, by Jon
Bentley, column 4, "Writing Correct Programs", p. 34:

     "Most programmers think that ... writing [binary search] s easy.
     They're wrong....

     "Given ample time, only about ten percent of professional
     programmers were able to get this small program right.  But they
     aren't the only ones to find this task difficult: in the history
     of Section 6.2.1 of his \emph{Sorting and Searching}, Knuth
     points out that while the first binary search was published in
     1946, the first published binary search without bugs did not
     appear until 1962."

Thanks,
Ricardo Anguiano             anguiano@codesourcery.com
CodeSourcery, LLC            http://www.codesourcery.com