Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Any undefined behavior??? (http://www.velocityreviews.com/forums/t444214-any-undefined-behavior.html)

Alan Schroeder 09-02-2006 07:02 PM

Any undefined behavior???
 
The following code produces the expected results on a PC using gcc, but I
need to port it (or least something similar) to a different
platform/compiler. I don't think I've introduced any undefined behavior but
would like another set of eyes to check.


#include <math.h>
#include <stdlib.h>

extern float window;

/*
* NOTE:
* This function will return the lowest index into 'data' which contains
* a value such that data[index]>=value-window, or -1 if a value can not
* be found such that data[index]>=value-window and
value+window<=data[index].
*/
int
find_first_index(const float *value, const float *data, size_t size, size_t
width)
{
int index;
float *fptr;
float minValue;

index = -1;
fptr = bsearch(value, data, size, width, compare_window);
if (fptr != NULL) {
minValue = *value - window;
index = (int)(fptr-data);
while (index > 0 && data[index] > minValue) {
index--;
}
if (index) index++; /* We may have gone one too far */
}
return index;
}

/*
* NOTE:
* **ONLY** use this function to sort an array of floats; it won't work
* as expected if searching for a arbitrary value.
*/
int
compare_exact(const void *e1, const void *e2)
{
const float *f1 = e1;
const float *f2 = e2;
float delta;

delta = *f1 - *f2;

if (delta < 0.0) return -1 ;
if (delta > 0.0) return 1;
return 0;
}

/*
* This function can be use with 'bsearch' to find a float value within
* a given +/- window
*/
int
compare_window(const void *e1, const void *e2)
{
const float *f1 = e1;
const float *f2 = e2;
float delta;

delta = *f1 - *f2;
if (fabs(delta) <= window) return 0;

if (delta < 0.0) return -1;
if (delta > 0.0) return 1;
/* NOTE: We should **NEVER** get here */
return 0;
}


Thanks,
ALS



Tim Prince 09-02-2006 07:50 PM

Re: Any undefined behavior???
 
Alan Schroeder wrote:
> The following code produces the expected results on a PC using gcc, but I
> need to port it (or least something similar) to a different
> platform/compiler. I don't think I've introduced any undefined behavior but
> would like another set of eyes to check.


It doesn't compile with any of 3 versions of gcc on my PCC. I suppose
that qualifies as no undefined behavior.

Eric Sosman 09-02-2006 08:25 PM

Re: Any undefined behavior???
 
Alan Schroeder wrote:
> The following code produces the expected results on a PC using gcc, but I
> need to port it (or least something similar) to a different
> platform/compiler. I don't think I've introduced any undefined behavior but
> would like another set of eyes to check.


I see only one probable blunder, but there are a few other
peculiarities, too. See below.

>
> #include <math.h>
> #include <stdlib.h>
>
> extern float window;
>
> /*
> * NOTE:
> * This function will return the lowest index into 'data' which contains
> * a value such that data[index]>=value-window, or -1 if a value can not
> * be found such that data[index]>=value-window and
> value+window<=data[index].
> */


"When the comments and the code disagree, both are
probably wrong." Maybe not in this case; I think it's
likely that the comment is just garbled and that the code
works as intended. Still, it's worth examining.

(My objection is that if window is non-negative, as
suggested by the way compare_window() is written, then
the condition value+window<=data[index] implies the condition
data[index]>=value-window. The search actually looks for a
value satisfying a pair of conditions that aren't redundant,
so there's something wrong here.)

> int
> find_first_index(const float *value, const float *data, size_t size, size_t
> width)
> {
> int index;
> float *fptr;
> float minValue;
>
> index = -1;
> fptr = bsearch(value, data, size, width, compare_window);
> if (fptr != NULL) {
> minValue = *value - window;
> index = (int)(fptr-data);
> while (index > 0 && data[index] > minValue) {
> index--;
> }


This looks weird. I can imagine three circumstances:

- width is always sizeof(float), and all the elements of
the data array are searched equally. If this is the case,
width should not be a function argument; what happens if
some caller supplies width=3?

- width is a multiple of sizeof(float), and bsearch looks
only at the first of each group of N=width/sizeof(float)
elements. (Maybe data really contains N-place vectors
strung end-to-end.) If so, then you should be stepping
index by N, not by 1. Also, it would be better to accept
the width argument as N rather than as N*sizeof(float),
and make the adjustment in the bsearch call -- again,
think about the caller providing width=42.

- width is N*sizeof(float) as above, but the intermediate
un-bsearched values are "bunched" within window of the
bsearched values. That's a peculiar enough arrangement
that it deserves a big fat comment.

> if (index) index++; /* We may have gone one too far */


Here's what I think is the blunder. If you bsearch for a
value that is exactly window greater than one of the array
elements, bsearch may find that array element. ("May," not
"will," because it could find a nearby element if they're
spaced less than window apart.) Then the while loop will not
iterate, and index will be as it was when calculated from the
bsearch result -- and then if index>0 you'll increment it.
This will violate the "lowest index" part of the function's
contract, and may also violate the range conditions (if the
original data[index]==value-window, then data[++index] might
equal value+1000*window.) If bsearch finds the topmost array
element, index is computed as size-1 and perhaps incremented
to size, which smells very much like an off-the-end error.
(If the "active" part of the data array is supposed to be
followed by one or more "inactive" values, that'a another
special situation deserving of a comment.)

> }
> return index;
> }
>
> /*
> * NOTE:
> * **ONLY** use this function to sort an array of floats; it won't work
> * as expected if searching for a arbitrary value.
> */
> int
> compare_exact(const void *e1, const void *e2)
> {
> const float *f1 = e1;
> const float *f2 = e2;
> float delta;
>
> delta = *f1 - *f2;


Possible overflow here if the array contains large positive
and large negative values. Possible loss of significance, which
I think is probably harmless in this setting (but which I haven't
studied thoroughly).

> if (delta < 0.0) return -1 ;
> if (delta > 0.0) return 1;
> return 0;


Consider avoiding all those worries about overflow and
significance loss by sticking to the comparison operators and
getting rid of the subtraction. You could write simply

if (*f1 < *f2) return -1;
if (*f1 > *f2) return +1;
return 0;

or you might opt for a one-liner only a C addict could love

return (*f1 > *f2) - (*f1 < *f2);

> }
>
> /*
> * This function can be use with 'bsearch' to find a float value within
> * a given +/- window
> */
> int
> compare_window(const void *e1, const void *e2)
> {
> const float *f1 = e1;
> const float *f2 = e2;
> float delta;
>
> delta = *f1 - *f2;


Possible overflow, as above.

> if (fabs(delta) <= window) return 0;
>
> if (delta < 0.0) return -1;
> if (delta > 0.0) return 1;
> /* NOTE: We should **NEVER** get here */


If you're so certain, call abort(). ;-)

Better, whenever the arrangement of your tests produces
a branch that cannot be taken, it's usually a sign that there
is something amiss with the branching logic. In this case,
you've observed that one of the tests above must fire, which
means there's no reason to make the third test: the fact that
the first two didn't fire makes the result of the third a
foregone conclusion, right?

Consider rearranging the tests, perhaps along these lines:

if (delta < -window) return -1;
if (delta > +window) return +1;
return 0;

or the C addict's methadone

return (*f1 >= *f2-window) - (*f1 <= *f2+window);

> return 0;
> }


If I were writing this, I think I'd just forget about
bsearch and write my own binary search in open code. Yes,
they'd both be "binary search" -- but bsearch is a binary
search specialized for strict equality, which isn't what
you want. You're not guilty of using a hammer to drive
screws, but you may be using a tack-hammer when you ought
to use a ball-peen hammer.

--
Eric Sosman
esosman@acm-dot-org.invalid

pete 09-03-2006 12:33 AM

Re: Any undefined behavior???
 
Eric Sosman wrote:
>
> Alan Schroeder wrote:
> > The following code produces the expected results on a PC using gcc, but I
> > need to port it (or least something similar) to a different
> > platform/compiler. I don't think I've introduced any undefined behavior but
> > would like another set of eyes to check.

>
> I see only one probable blunder, but there are a few other
> peculiarities, too. See below.
>
> >
> > #include <math.h>
> > #include <stdlib.h>
> >
> > extern float window;
> >
> > /*
> > * NOTE:
> > * This function will return the lowest index into 'data' which contains
> > * a value such that data[index]>=value-window, or -1 if a value can not
> > * be found such that data[index]>=value-window and
> > value+window<=data[index].
> > */

>
> "When the comments and the code disagree, both are
> probably wrong." Maybe not in this case; I think it's
> likely that the comment is just garbled and that the code
> works as intended. Still, it's worth examining.
>
> (My objection is that if window is non-negative, as
> suggested by the way compare_window() is written, then
> the condition value+window<=data[index] implies the condition
> data[index]>=value-window. The search actually looks for a
> value satisfying a pair of conditions that aren't redundant,
> so there's something wrong here.)
>
> > int
> > find_first_index(const float *value, const float *data, size_t size, size_t
> > width)
> > {
> > int index;
> > float *fptr;
> > float minValue;
> >
> > index = -1;
> > fptr = bsearch(value, data, size, width, compare_window);
> > if (fptr != NULL) {
> > minValue = *value - window;
> > index = (int)(fptr-data);
> > while (index > 0 && data[index] > minValue) {
> > index--;
> > }

>
> This looks weird. I can imagine three circumstances:
>
> - width is always sizeof(float), and all the elements of
> the data array are searched equally. If this is the case,
> width should not be a function argument; what happens if
> some caller supplies width=3?
>
> - width is a multiple of sizeof(float), and bsearch looks
> only at the first of each group of N=width/sizeof(float)
> elements. (Maybe data really contains N-place vectors
> strung end-to-end.) If so, then you should be stepping
> index by N, not by 1. Also, it would be better to accept
> the width argument as N rather than as N*sizeof(float),
> and make the adjustment in the bsearch call -- again,
> think about the caller providing width=42.
>
> - width is N*sizeof(float) as above, but the intermediate
> un-bsearched values are "bunched" within window of the
> bsearched values. That's a peculiar enough arrangement
> that it deserves a big fat comment.
>
> > if (index) index++; /* We may have gone one too far */

>
> Here's what I think is the blunder. If you bsearch for a
> value that is exactly window greater than one of the array
> elements, bsearch may find that array element. ("May," not
> "will," because it could find a nearby element if they're
> spaced less than window apart.) Then the while loop will not
> iterate, and index will be as it was when calculated from the
> bsearch result -- and then if index>0 you'll increment it.
> This will violate the "lowest index" part of the function's
> contract, and may also violate the range conditions (if the
> original data[index]==value-window, then data[++index] might
> equal value+1000*window.) If bsearch finds the topmost array
> element, index is computed as size-1 and perhaps incremented
> to size, which smells very much like an off-the-end error.
> (If the "active" part of the data array is supposed to be
> followed by one or more "inactive" values, that'a another
> special situation deserving of a comment.)
>
> > }
> > return index;
> > }
> >
> > /*
> > * NOTE:
> > * **ONLY** use this function to sort an array of floats; it won't work
> > * as expected if searching for a arbitrary value.
> > */
> > int
> > compare_exact(const void *e1, const void *e2)
> > {
> > const float *f1 = e1;
> > const float *f2 = e2;
> > float delta;
> >
> > delta = *f1 - *f2;

>
> Possible overflow here if the array contains large positive
> and large negative values. Possible loss of significance, which
> I think is probably harmless in this setting (but which I haven't
> studied thoroughly).
>
> > if (delta < 0.0) return -1 ;
> > if (delta > 0.0) return 1;
> > return 0;

>
> Consider avoiding all those worries about overflow and
> significance loss by sticking to the comparison operators and
> getting rid of the subtraction. You could write simply
>
> if (*f1 < *f2) return -1;
> if (*f1 > *f2) return +1;
> return 0;
>
> or you might opt for a one-liner only a C addict could love
>
> return (*f1 > *f2) - (*f1 < *f2);


or my favorite:

return *f2 > *f1 ? -1 : *f2 != *f1;


--
pete

Barry Schwarz 09-03-2006 02:39 AM

Re: Any undefined behavior???
 
On Sat, 2 Sep 2006 15:02:40 -0400, "Alan Schroeder"
<alschroeder@comcast.net> wrote:

>The following code produces the expected results on a PC using gcc, but I
>need to port it (or least something similar) to a different
>platform/compiler. I don't think I've introduced any undefined behavior but
>would like another set of eyes to check.
>
>
>#include <math.h>
>#include <stdlib.h>
>
>extern float window;
>
>/*
> * NOTE:
> * This function will return the lowest index into 'data' which contains
> * a value such that data[index]>=value-window, or -1 if a value can not
> * be found such that data[index]>=value-window and
>value+window<=data[index].
> */
>int
>find_first_index(const float *value, const float *data, size_t size, size_t
>width)
>{
> int index;
> float *fptr;
> float minValue;
>
> index = -1;
> fptr = bsearch(value, data, size, width, compare_window);


compare_window is not declared at this point.

> if (fptr != NULL) {
> minValue = *value - window;
> index = (int)(fptr-data);
> while (index > 0 && data[index] > minValue) {


If multiple entries have the value minValue, you stop too soon (or the
comment about >= is incorrect).

> index--;
> }
> if (index) index++; /* We may have gone one too far */
> }
> return index;
>}
>

snip


Remove del for email

ena8t8si@yahoo.com 09-03-2006 08:17 AM

Re: Any undefined behavior???
 

Alan Schroeder wrote:
> The following code produces the expected results on a PC using gcc, but I
> need to port it (or least something similar) to a different
> platform/compiler. I don't think I've introduced any undefined behavior but
> would like another set of eyes to check.
>
>
> #include <math.h>
> #include <stdlib.h>
>
> extern float window;
>
> /*
> * NOTE:
> * This function will return the lowest index into 'data' which contains
> * a value such that data[index]>=value-window, or -1 if a value can not
> * be found such that data[index]>=value-window and
> value+window<=data[index].
> */
> int
> find_first_index(const float *value, const float *data, size_t size, size_t
> width)


If what you want is: given window >= 0, find least index so that
*value-window <= data[index] && data[index] <= *value+window
(with entries in data being in non-decreasing order)

{
double vm = *value - window;
double vp = *value + window;
int a, b, c;
assert( window>=0 );
if (width<=0) return -1;

for ( a = -1, c = width-1; a+1 < c; ) {
b = (a+c)/2;
if (data[b] < vm) a = b;
else c = b;
}
assert( a == -1 || data[a] < vm);
assert( c == width-1 || vm <= data[c] );
if (vm <= data[c] && data[c] <= vp) return c;
return -1;
}


If what you want is: given window >= 0, find least index so that
*value-window <= data[index] && *value+window <= data[index]
(with entries in data being in non-decreasing order)

{
double vp = *value + window;
int a, b, c;
assert( window>=0 );
if (width<=0) return -1;

for ( a = -1, c = width-1; a+1 < c; ) {
b = (a+c)/2;
if (data[b] < vp) a = b;
else c = b;
}
assert( a == -1 || data[a] < vp);
assert( c == width-1 || vp <= data[c] );
assert( *value - window <= vp );
if (vp <= data[c]) return c;
return -1;
}


Ben C 09-03-2006 10:35 PM

Re: Any undefined behavior???
 
On 2006-09-02, Alan Schroeder <alschroeder@comcast.net> wrote:
> The following code produces the expected results on a PC using gcc, but I
> need to port it (or least something similar) to a different
> platform/compiler. I don't think I've introduced any undefined behavior but
> would like another set of eyes to check.
>
>
> #include <math.h>
> #include <stdlib.h>
>
> extern float window;
>
> /*
> * NOTE:
> * This function will return the lowest index into 'data' which contains
> * a value such that data[index]>=value-window, or -1 if a value can not
> * be found such that data[index]>=value-window and
> value+window<=data[index].
> */
> int
> find_first_index(const float *value, const float *data, size_t size, size_t
> width)
> {


> [...]


>
> index = -1;
> fptr = bsearch(value, data, size, width, compare_window);


I know you didn't ask for style comments, only about undefined
behaviour, but I think this would be clearer like this:

int
find_first_index(float value, const float *data, size_t n)
{
...
fptr = bsearch(&value, data, n, sizeof *data, compare_window);
}

We're always searching a float array here, so having the "width"
parameter just seems to make life unnecessarily difficult for the
caller. It's not telling us anything we don't know.

The const float * parameter also looks at first glance like an array
(why else would a const pointer to a builtin type be in an argument
list?). bsearch takes a pointer because it's generic, but you can just
take the address at the point of calling it.

> if (fptr != NULL) {
> minValue = *value - window;
> index = (int)(fptr-data);
> while (index > 0 && data[index] > minValue) {
> index--;
> }
> if (index) index++; /* We may have gone one too far */
> }
> return index;


I think here you could use ptrdiff_t for index instead of int. After all
you're using size_t for the array lengths. But there's nothing undefined
about using int (as far as I know).

> [...]


> int
> compare_exact(const void *e1, const void *e2)
> {
> const float *f1 = e1;
> const float *f2 = e2;
> float delta;
>
> delta = *f1 - *f2;
>
> if (delta < 0.0) return -1 ;
> if (delta > 0.0) return 1;


This is not undefined, but you might want to put 0.0f instead of 0.0 if
you anticipate porting to a machine with fast floats but software double
precision routines.

Alan Schroeder 09-04-2006 01:18 PM

Re: Any undefined behavior???
 

"Eric Sosman" <esosman@acm-dot-org.invalid> wrote in message
news:yYqdnZvmoc99dWTZnZ2dnUVZ_sidnZ2d@comcast.com. ..
> Alan Schroeder wrote:
>> The following code produces the expected results on a PC using gcc, but I
>> need to port it (or least something similar) to a different
>> platform/compiler. I don't think I've introduced any undefined behavior
>> but would like another set of eyes to check.

>
> I see only one probable blunder, but there are a few other
> peculiarities, too. See below.
>
>>
>> #include <math.h>
>> #include <stdlib.h>
>>
>> extern float window;
>>
>> /*
>> * NOTE:
>> * This function will return the lowest index into 'data' which
>> contains
>> * a value such that data[index]>=value-window, or -1 if a value can
>> not
>> * be found such that data[index]>=value-window and
>> value+window<=data[index].
>> */

>
> "When the comments and the code disagree, both are
> probably wrong." Maybe not in this case; I think it's
> likely that the comment is just garbled and that the code
> works as intended. Still, it's worth examining.
>
> (My objection is that if window is non-negative, as
> suggested by the way compare_window() is written, then
> the condition value+window<=data[index] implies the condition
> data[index]>=value-window. The search actually looks for a
> value satisfying a pair of conditions that aren't redundant,
> so there's something wrong here.)


It's probaly the comment. I didn't think I had stated the intention
correctly. I'll get the comment right.

>
>> int
>> find_first_index(const float *value, const float *data, size_t size,
>> size_t width)
>> {
>> int index;
>> float *fptr;
>> float minValue;
>>
>> index = -1;
>> fptr = bsearch(value, data, size, width, compare_window);
>> if (fptr != NULL) {
>> minValue = *value - window;
>> index = (int)(fptr-data);
>> while (index > 0 && data[index] > minValue) {
>> index--;
>> }

>
> This looks weird. I can imagine three circumstances:
>
> - width is always sizeof(float), and all the elements of
> the data array are searched equally. If this is the case,
> width should not be a function argument; what happens if
> some caller supplies width=3?
>
> - width is a multiple of sizeof(float), and bsearch looks
> only at the first of each group of N=width/sizeof(float)
> elements. (Maybe data really contains N-place vectors
> strung end-to-end.) If so, then you should be stepping
> index by N, not by 1. Also, it would be better to accept
> the width argument as N rather than as N*sizeof(float),
> and make the adjustment in the bsearch call -- again,
> think about the caller providing width=42.
>
> - width is N*sizeof(float) as above, but the intermediate
> un-bsearched values are "bunched" within window of the
> bsearched values. That's a peculiar enough arrangement
> that it deserves a big fat comment.
>


I simplified the code to just use an array of floats. The actual data will
be different structs with the first element of each struct a float. You're
probably right and I'll comment the code better.

> > if (index) index++; /* We may have gone one too far */

>
> Here's what I think is the blunder. If you bsearch for a
> value that is exactly window greater than one of the array
> elements, bsearch may find that array element. ("May," not
> "will," because it could find a nearby element if they're
> spaced less than window apart.) Then the while loop will not
> iterate, and index will be as it was when calculated from the
> bsearch result -- and then if index>0 you'll increment it.
> This will violate the "lowest index" part of the function's
> contract, and may also violate the range conditions (if the
> original data[index]==value-window, then data[++index] might
> equal value+1000*window.) If bsearch finds the topmost array
> element, index is computed as size-1 and perhaps incremented
> to size, which smells very much like an off-the-end error.
> (If the "active" part of the data array is supposed to be
> followed by one or more "inactive" values, that'a another
> special situation deserving of a comment.)
>


That's another area I had problems with, if data[index]==value-window,
should I return index or index-1. I guess I'll have to check and get a
little better requirement definition. My guess is it's better to return a
range too large and eliminate the extra data later than to miss a possible
match.

>> }
>> return index;
>> }
>>
>> /*
>> * NOTE:
>> * **ONLY** use this function to sort an array of floats; it won't
>> work
>> * as expected if searching for a arbitrary value.
>> */
>> int
>> compare_exact(const void *e1, const void *e2)
>> {
>> const float *f1 = e1;
>> const float *f2 = e2;
>> float delta;
>>
>> delta = *f1 - *f2;

>
> Possible overflow here if the array contains large positive
> and large negative values. Possible loss of significance, which
> I think is probably harmless in this setting (but which I haven't
> studied thoroughly).
>
>> if (delta < 0.0) return -1 ;
>> if (delta > 0.0) return 1;
>> return 0;

>
> Consider avoiding all those worries about overflow and
> significance loss by sticking to the comparison operators and
> getting rid of the subtraction. You could write simply
>
> if (*f1 < *f2) return -1;
> if (*f1 > *f2) return +1;
> return 0;
>
> or you might opt for a one-liner only a C addict could love
>
> return (*f1 > *f2) - (*f1 < *f2);
>
>> }
>>
>> /*
>> * This function can be use with 'bsearch' to find a float value within
>> * a given +/- window
>> */
>> int
>> compare_window(const void *e1, const void *e2)
>> {
>> const float *f1 = e1;
>> const float *f2 = e2;
>> float delta;
>>
>> delta = *f1 - *f2;

>
> Possible overflow, as above.
>
>> if (fabs(delta) <= window) return 0;
>>
>> if (delta < 0.0) return -1;
>> if (delta > 0.0) return 1;
>> /* NOTE: We should **NEVER** get here */

>
> If you're so certain, call abort(). ;-)
>
> Better, whenever the arrangement of your tests produces
> a branch that cannot be taken, it's usually a sign that there
> is something amiss with the branching logic. In this case,
> you've observed that one of the tests above must fire, which
> means there's no reason to make the third test: the fact that
> the first two didn't fire makes the result of the third a
> foregone conclusion, right?
>
> Consider rearranging the tests, perhaps along these lines:
>
> if (delta < -window) return -1;
> if (delta > +window) return +1;
> return 0;
>
> or the C addict's methadone
>
> return (*f1 >= *f2-window) - (*f1 <= *f2+window);
>
>> return 0;
>> }

>
> If I were writing this, I think I'd just forget about
> bsearch and write my own binary search in open code. Yes,
> they'd both be "binary search" -- but bsearch is a binary
> search specialized for strict equality, which isn't what
> you want. You're not guilty of using a hammer to drive
> screws, but you may be using a tack-hammer when you ought
> to use a ball-peen hammer.
>
> --
> Eric Sosman
> esosman@acm-dot-org.invalid


I'd thought about rolling my own binary serarch function, but I've seen
enough in-house versions mess up the search, I decided to go with the
library function. I'll have to think about coding the search routine after
I fix the other problems.

Thanks again for your help,
ALS



ena8t8si@yahoo.com 09-06-2006 10:03 AM

Re: Any undefined behavior???
 

Alan Schroeder wrote:
> "Eric Sosman" <esosman@acm-dot-org.invalid> wrote in message

....
> > If I were writing this, I think I'd just forget about
> > bsearch and write my own binary search in open code. Yes,
> > they'd both be "binary search" -- but bsearch is a binary
> > search specialized for strict equality, which isn't what
> > you want. You're not guilty of using a hammer to drive
> > screws, but you may be using a tack-hammer when you ought
> > to use a ball-peen hammer.

>
> I'd thought about rolling my own binary serarch function, but I've seen
> enough in-house versions mess up the search, I decided to go with the
> library function. ...


Then this is an opportunity not only to write a shorter and
simpler function but also raise the level of understanding
for your coworkers. The original code has problems not only
because of the little glitches but because it's overly
complicated. Also, as Eric Sosman pointed out, if bsearch()
deals with values that are "equal", which one it finds is
unspecified.

/* Method to find first index in array of structured
* floating values so that vm <= array[index] <= vp,
* where vm = *value - window
* and vp = *value + window
*
* Establish invariant:
*
* 0 <= a && a <= c && c <= n
* a == 0 || float_data[a-1] < vm
* c == n || vm <= float_data[c-1]
*
* where float_data[i] == *(float*)(fp + i*size)
*
* Then do the while loop that does the binary search, whereupon
*
* n < 1 || a == c-1
*
* The above assertion, plus the invariant, plus
* the array being sorted, means float_data[a] is
* the only possible candidate.
*/

int find_first_index( const float *value,
const float *data,
size_t size,
size_t n )
{
unsigned a, b, c;
const double vm = *value - window;
const double vp = *value + window;
const unsigned char *const fp = (const unsigned char*)data;

a = 0, c = n;
assert( a <= c && c <= n );
assert( a == 0 || *(float*)(fp + (a-1)*size) < vm );
assert( c == n || *(float*)(fp + (c-1)*size) >= vm );

while (a+1 < c) {
b = a + (c-a)/2;
assert( a < b && b < c );

if (*(float*)(fp + (b-1)*size) < vm) a = b;
else c = b;

assert( a <= c && c <= n );
assert( a == 0 || *(float*)(fp + (a-1)*size) < vm );
assert( c == n || *(float*)(fp + (c-1)*size) >= vm );
}

assert( n < 1 || a == c-1 );

if (n < 1) return -1;
if (*(float*)(fp + a*size) < vm) return -1;
if (*(float*)(fp + a*size) > vp) return -1;

return a;
}


pete 09-08-2006 02:29 AM

Re: Any undefined behavior???
 
Ben C wrote:
>
> On 2006-09-02, Alan Schroeder <alschroeder@comcast.net> wrote:


> > int
> > compare_exact(const void *e1, const void *e2)
> > {
> > const float *f1 = e1;
> > const float *f2 = e2;
> > float delta;
> >
> > delta = *f1 - *f2;
> >
> > if (delta < 0.0) return -1 ;
> > if (delta > 0.0) return 1;

>
> This is not undefined,
> but you might want to put 0.0f instead of 0.0 if
> you anticipate porting to a machine with fast floats
> but software double precision routines.


Comparing zero to delta is dopey.
There's no point in optimizing that comparison.

*f1 should be compared to *f2 directly.

--
pete


All times are GMT. The time now is 05:35 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.