Expert-Q: (a!=b) != memcmp(&a,&b,sizeof a) ?
Helmut Leitner
(e.g. int, long, float, double ...).
On many platforms it is possible to replace the
comparisions
a==b
a!=b
by
memcmp(&a,&b,sizeof(a))==0
memcmp(&a,&b,sizeof(a))
What are the conditions that this will not yield the
desired results?
Can someone give (an) implementation example(s), where
the reasons for this behaviour can be seen?
The background is the wish of fast and easy comparison
of multicomponent structures (within a perfect hash system):
typedef struct test {
char ...
int ...
float ...
...
} TEST;
TEST sa,sb;
memset(&sa,'\0',sizeof(TEST)); /* or TestClear(&sa); */
memset(&sb,'\0',sizeof(TEST)); /* or TestClear(&sb); */
...
any standard component assignment. /* or TestSetComponent(&sa,comp) */
...
memcmp(&sa,&sb,sizeof(TEST));
Is it possible to construct such a general system to work
in a portable way on all platforms?
Would it be possible to construct an #if-expression
#if (expression_memcmp_will_do_the_job)
TestEqu(psa,psb) (memcmp(psa,psb,sizeof(TEST))==0)
#else
(psa->comp1==psb->comp2 && psa->comp2==psb->comp2 && .... )
#endif
to react to the different situations?
--
Helmut Leitner lei...@hls.via.at
Graz, Austria www.hls-software.com
Paul Mesken
<lei...@hls.via.at> wrote:
>Let's assume that a and b have the same basic data type
>(e.g. int, long, float, double ...).
>
>On many platforms it is possible to replace the
>comparisions
> a==b
> a!=b
>by
> memcmp(&a,&b,sizeof(a))==0
> memcmp(&a,&b,sizeof(a))
>
If a and b are of the same basic data type then you wouldn't do this.
It's ugly and probably slower. Besides: what if a and/or b have the
storage class specifier "register"? Then it is illegal to use the
address-of operator on them.
>What are the conditions that this will not yield the
>desired results?
>
If they are not of the same basic type for example. Unlike using the
equality operators, the memcmp version will not convert them. This
might result in inequality while the values of a and b are the same.
It might look as if the memcmp version can do "clever" comparisons
since it would also accept derived types like structures but even if a
and b are of the same derived type you would still run the risk of
inequality in the case of inequal values in the padding (if any).
Thus, inequality might even appear for structures that are of the same
type and have the same values for their members.
However:
>The background is the wish of fast and easy comparison
>of multicomponent structures (within a perfect hash system):
>
> typedef struct test {
> char ...
> int ...
> float ...
> ...
> } TEST;
>
> TEST sa,sb;
> memset(&sa,'\0',sizeof(TEST)); /* or TestClear(&sa); */
> memset(&sb,'\0',sizeof(TEST)); /* or TestClear(&sb); */
> ...
> any standard component assignment. /* or TestSetComponent(&sa,comp) */
> ...
> memcmp(&sa,&sb,sizeof(TEST));
>
Yes, you first set all char's of the structures to zero. This solves
the problem of the "uninitialized padding".
>Is it possible to construct such a general system to work
>in a portable way on all platforms?
>
In this particular case I don't see why not.
>Would it be possible to construct an #if-expression
>
> #if (expression_memcmp_will_do_the_job)
> TestEqu(psa,psb) (memcmp(psa,psb,sizeof(TEST))==0)
> #else
> (psa->comp1==psb->comp2 && psa->comp2==psb->comp2 && .... )
> #endif
>
>to react to the different situations?
I don't see how the expression should look like. Your solution works
as long as you take care to initialize _all_ char's of the structures
to avoid the "inequal padding value" problem and make sure that your a
and b are of the same structure type.
Alex...@scitex.com
Helmut Leitner <lei...@hls.via.at> wrote:
> Let's assume that a and b have the same basic data type
> (e.g. int, long, float, double ...).
>
> On many platforms it is possible to replace the
> comparisions
> a==b
> a!=b
> by
> memcmp(&a,&b,sizeof(a))==0
> memcmp(&a,&b,sizeof(a))
>
> desired results?
I can think of two:
a) holes in data type representation
b) +0 and -0 for one's complement platforms
--
Regards,
Alex Krol
Disclaimer: I'm not speaking for Scitex Corporation Ltd
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
Christian Bau
> Let's assume that a and b have the same basic data type
> (e.g. int, long, float, double ...).
>
> On many platforms it is possible to replace the
> comparisions
> a==b
> a!=b
> by
> memcmp(&a,&b,sizeof(a))==0
> memcmp(&a,&b,sizeof(a))
Quite often it does not work with IEEE standard floating point numbers.
Especially with +0.0 and -0.0 (they compare equal, but have different bit
patterns) and NaN's (they compare different, even if they are identical).
There have been machines with long double = 80 bit + 16 unused bits, for
example the Motorola 68040 and 68020/30 with coprocessor. On these
machines you cannot rely on memcpy at all.
And for structs and unions you will always have a problem because of padding.
Apart from this, it will work on most machines :-(
Szu-Wen Huang
: Let's assume that a and b have the same basic data type
: (e.g. int, long, float, double ...).
: On many platforms it is possible to replace the
: comparisions
: a==b
: a!=b
: by
: memcmp(&a,&b,sizeof(a))==0
: memcmp(&a,&b,sizeof(a))
: What are the conditions that this will not yield the
: desired results?
: Can someone give (an) implementation example(s), where
: the reasons for this behaviour can be seen?
Sure. Recall the strange segment:offset scheme of addressing
on the 80x86 real mode, where the actual address is computed
as (segment * 16 + offset). Thus, many segment:offset pairs
actually compute to the same address, and the equality operator
for pointers must handle these. Typically, they normalize the
pointer before comparison.
Using memcmp() will likely produce false negatives.
: The background is the wish of fast and easy comparison
: of multicomponent structures (within a perfect hash system):
[...]
: Is it possible to construct such a general system to work
: in a portable way on all platforms?
In general, whenever more than one representation is possible
for a single value, your proposal will fail. If you use a
structure, you should also worry about the value of padding
bytes, which probably means a mandatory memset() after any
malloc().
: Would it be possible to construct an #if-expression
: #if (expression_memcmp_will_do_the_job)
: TestEqu(psa,psb) (memcmp(psa,psb,sizeof(TEST))==0)
: #else
: (psa->comp1==psb->comp2 && psa->comp2==psb->comp2 && .... )
: #endif
: to react to the different situations?
Isn't that even longer than just doing the comparison? :)
Paul Lutus
way on all platforms? >>
No, this is not possible. There are any number of reasons an entire
structure's components will not compare successfully, even though each of
the data components are comparable. Some have to do with differences between
platforms, some have to do with differences between structures on a single
platform.
Finally, you will try to compare a double and a float, arguing that they are
really the same number. If you compare them directly, you will get the
expected results. If you use memcmp(), you will not.
--
Paul Lutus
www.arachnoid.com
Helmut Leitner wrote in message <377738B4...@hls.via.at>...
>Let's assume that a and b have the same basic data type
>(e.g. int, long, float, double ...).
>
>On many platforms it is possible to replace the
>comparisions
> a==b
> a!=b
>by
> memcmp(&a,&b,sizeof(a))==0
> memcmp(&a,&b,sizeof(a))
>
>What are the conditions that this will not yield the
>desired results?
>
>Can someone give (an) implementation example(s), where
>the reasons for this behaviour can be seen?
>
>The background is the wish of fast and easy comparison
>of multicomponent structures (within a perfect hash system):
>
> typedef struct test {
> char ...
> int ...
> float ...
> ...
> } TEST;
>
> TEST sa,sb;
> memset(&sa,'\0',sizeof(TEST)); /* or TestClear(&sa); */
> memset(&sb,'\0',sizeof(TEST)); /* or TestClear(&sb); */
> ...
> any standard component assignment. /* or TestSetComponent(&sa,comp) */
> ...
> memcmp(&sa,&sb,sizeof(TEST));
>
>Is it possible to construct such a general system to work
>in a portable way on all platforms?
>
>Would it be possible to construct an #if-expression
>
> #if (expression_memcmp_will_do_the_job)
> TestEqu(psa,psb) (memcmp(psa,psb,sizeof(TEST))==0)
> #else
> (psa->comp1==psb->comp2 && psa->comp2==psb->comp2 && .... )
> #endif
>
>to react to the different situations?
>
FigBug
> really the same number. If you compare them directly, you will get the
> expected results. If you use memcmp(), you will not.
It's not clear to me what "compare them directly" means. Are you saying
you can compare a float to a double using '=='? You can't, it won't work
as expected.
FigBug
Dann Corbit
news:Pine.SUN.3.96.990628105138.16344A-100000@valdes...
You should not even compare a double to a double using ==. The C FAQ
addresses this:
14.5: What's a good way to check for "close enough" floating-point
equality?
A: Since the absolute accuracy of floating point values varies, by
definition, with their magnitude, the best way of comparing two
floating point values is to use an accuracy threshold which is
relative to the magnitude of the numbers being compared. Rather
than
double a, b;
...
if(a == b) /* WRONG */
use something like
#include <math.h>
if(fabs(a - b) <= epsilon * fabs(a))
for some suitably-chosen degree of closeness epsilon (as long as
a is nonzero!).
References: Knuth Sec. 4.2.2 pp. 217-8.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
Paul Lutus
having to do with the binary storage type, but the compiler will promote the
float to a double before making the comparison. This is not true for
memcmp(), my original point.
--
Paul Lutus
www.arachnoid.com
FigBug wrote in message ...
>> Finally, you will try to compare a double and a float, arguing that they
are
>> really the same number. If you compare them directly, you will get the
>> expected results. If you use memcmp(), you will not.
>
>It's not clear to me what "compare them directly" means. Are you saying
>you can compare a float to a double using '=='? You can't, it won't work
>as expected.
>
>FigBug
>
raw...@my-deja.com
FigBug <rra...@csc.UVic.CA> wrote:
> > Finally, you will try to compare a double and a float, arguing that they are
> > really the same number. If you compare them directly, you will get the
> > expected results. If you use memcmp(), you will not.
>
> It's not clear to me what "compare them directly" means. Are you saying
> you can compare a float to a double using '=='? You can't, it won't work
> as expected.
It depends on how it's expected to work. You can compare a
float and a double, and of course then the float gets converted
to a double. The values are compared, and == must take into
account the possibility of different representations for the same
value. For memcmp, objects holding the two values probably
wouldn't even have the same size.
(Round off errors could also cause unexpected results,
but this is true of comparisons of two doubles as well and
memcmp is not going to help the situation at all. You could
consider an int and a long instead without changing the point.)
--
MJSR
FigBug
> It depends on how it's expected to work. You can compare a
> float and a double, and of course then the float gets converted
> to a double. The values are compared, and == must take into
> account the possibility of different representations for the same
> value. For memcmp, objects holding the two values probably
> wouldn't even have the same size.
>
> (Round off errors could also cause unexpected results,
> but this is true of comparisons of two doubles as well and
> memcmp is not going to help the situation at all. You could
> consider an int and a long instead without changing the point.)
The point I was attemping to make was, that the following is useful:
int i;
long int li;
i = 1;
li = 1;
if (i == li) blaa();
and the following won't do anything usefull:
float f;
double d;
f = 1.1;
d = 1.1;
if (f == d) blaa();
Paul's post was unclear, it seemed to claim (to me anyway) that doing the
above was usefull.
FigBug
Lawrence Kirby
lei...@hls.via.at "Helmut Leitner" writes:
>Let's assume that a and b have the same basic data type
>(e.g. int, long, float, double ...).
>
>On many platforms it is possible to replace the
>comparisions
> a==b
> a!=b
>by
> memcmp(&a,&b,sizeof(a))==0
> memcmp(&a,&b,sizeof(a))
>
>What are the conditions that this will not yield the
>desired results?
When different bit patterns represent the same value or at least
values that compare equal. There are various reasons why this might
happen.
Firstly any basic type except unsigned char can have "holes" or unused
bits that don't contribute to the value. So these bits can differ (hence
memcmp() will return non-zero) for values that compare equal.
In 1's complement and sign-mangitde format integers 0 and -0 have
different bit representations but compare equal.
In floating point formats such as IEEE-754 there can also be different
representations for 0 and -0. I believe in some floating point
formats there are a large number of representations for zero. Some
floating point formats such as IEEE-754 also create the opposite
problem, NaNs compare unquual to anything even other NaNs so it is possible
for values with identical bit patterns to compare unequal.
Pointers can have different representations for the same address (e.g.
in segnemted archatectures like the 8086). They can also contain other
information such as boundary information (these are sometimes called fat
pointers). So pointers with different bit patterns can compare equal.
Structures and unions can include padding bytes. Since padding does not
contribute to the structure or union's value I don't see anything that
prohibits this padding from changing arbitrarily. There can also be
padding bits where bit-fields are involved.
>Can someone give (an) implementation example(s), where
>the reasons for this behaviour can be seen?
>
>The background is the wish of fast and easy comparison
>of multicomponent structures (within a perfect hash system):
>
> typedef struct test {
> char ...
> int ...
> float ...
> ...
> } TEST;
>
> TEST sa,sb;
> memset(&sa,'\0',sizeof(TEST)); /* or TestClear(&sa); */
> memset(&sb,'\0',sizeof(TEST)); /* or TestClear(&sb); */
> ...
> any standard component assignment. /* or TestSetComponent(&sa,comp) */
> ...
> memcmp(&sa,&sb,sizeof(TEST));
>
>Is it possible to construct such a general system to work
>in a portable way on all platforms?
No.
>Would it be possible to construct an #if-expression
>
> #if (expression_memcmp_will_do_the_job)
> TestEqu(psa,psb) (memcmp(psa,psb,sizeof(TEST))==0)
> #else
> (psa->comp1==psb->comp2 && psa->comp2==psb->comp2 && .... )
> #endif
>
>to react to the different situations?
Probably the simplest thing to do would be to veryify the platforms
you are interested in yourself and define a macro you can test for
those platforms which fit the bill. However there are lots of
different ways to fail.
--
-----------------------------------------
Lawrence Kirby | fr...@genesis.demon.co.uk
Wilts, England | 7073...@compuserve.com
-----------------------------------------
Lawrence Kirby
usu...@euronet.nl "Paul Mesken" writes:
>On Mon, 28 Jun 1999 10:56:20 +0200, Helmut Leitner
><lei...@hls.via.at> wrote:
>
>>Let's assume that a and b have the same basic data type
>>(e.g. int, long, float, double ...).
>>
>>On many platforms it is possible to replace the
>>comparisions
>> a==b
>> a!=b
>>by
>> memcmp(&a,&b,sizeof(a))==0
>> memcmp(&a,&b,sizeof(a))
>>
>If a and b are of the same basic data type then you wouldn't do this.
>It's ugly and probably slower. Besides: what if a and/or b have the
>storage class specifier "register"? Then it is illegal to use the
>address-of operator on them.
The simple fix for that is to remove the register specifier. If you
are writing the function containing the memcmpĸcall you should have
control of the local variables in the function.
Paul Lutus
to claim (to me anyway) that doing the above was usefull. >>
It *is* useful. Typically the programmer will know the float will be
converted to a double, then compared to a double. Acknowledging the various
possible errors not related to the problem at hand, in many cases this is
the same as comparing two doubles.
And, granted the limitations of direct comparison of floating-point data
types, it cannot meaningfully be replaced with the memcmp() approach.
--
Paul Lutus
www.arachnoid.com
FigBug wrote in message ...
Dann Corbit
news:TJUd3.97171$_m4.1...@news2.giganews.com...
> << [about comparing a float and a double] Paul's post was unclear, it
seemed
> to claim (to me anyway) that doing the above was usefull. >>
>
> It *is* useful. Typically the programmer will know the float will be
> converted to a double, then compared to a double. Acknowledging the
various
> possible errors not related to the problem at hand, in many cases this is
> the same as comparing two doubles.
indicates that the programmer is probably incompetent for numerical work.
> And, granted the limitations of direct comparison of floating-point data
> types, it cannot meaningfully be replaced with the memcmp() approach.
Hopefully, it will be replaced with something useful.
Lawrence Kirby
nos...@nosite.com "Paul Lutus" writes:
...
>Finally, you will try to compare a double and a float, arguing that they are
>really the same number. If you compare them directly, you will get the
>expected results. If you use memcmp(), you will not.
This isn't a problem since...
>Helmut Leitner wrote in message <377738B4...@hls.via.at>...
>>Let's assume that a and b have the same basic data type
--
Helmut Leitner
Paul Lutus wrote:
>
> << Is it possible to construct such a general system to work in a portable
> way on all platforms? >>
>
> No, this is not possible.
> There are any number of reasons an entire structure's
> components will not compare successfully
> even though each of the data components are comparable.
Even if the whole data structure is "initialized" in
the best possible way (to be determined)?
> Some have to do with differences between platforms,
This is a bit cryptic to me. If there is no general, portable
way to make memcmp() work, then of course there must be differences
between platforms. But your statement doesn't tell anything...
> some have to do with differences between structures on a single platform.
If we define
struct test sa,sb;
and initialize them properly (to be determined)
TestClear(&sa);
TestClear(&sb);
what can be the differences between these structures.
> Finally, you will try to compare a double and a float
Look at my first sentence (the basic assumption):
"Let's assume that a and b have the same basic data type"
This clearly excludes comparing pears and apples.
Paul Lutus
way (to be determined)? >>
Yes. Consider otherwise acceptable data types for C comparisons, such as a
short and a long, or a float and a double (floating-point errors aside).
This is apart from any platform-related issues.
<< Look at my first sentence (the basic assumption): "Let's assume that a
and b have the same basic data type" This clearly excludes comparing pears
and apples. >>
Not at all, and complying C compilers have no objection. Example:
#include <stdio.h>
struct testA {
short orange;
long apple;
};
struct testB {
long orange;
short apple;
};
struct testC {
float orange;
double apple;
};
struct testD {
double orange;
float apple;
};
void testPrint(char *prompt, int v)
{
printf("%s: %s\n",prompt,(v)?"True":"False");
}
int main()
{
struct testA w = {333,333};
struct testB x = {333,333};
struct testC y = {333.125,333.125};
struct testD z = {333.125,333.125};
testPrint("member 1 comparison",(w.orange == x.orange));
testPrint("member 2 comparison",(w.apple == x.apple));
testPrint("memcmp() comparison", !memcmp(&w,&x,sizeof(w)));
testPrint("member 1 comparison",(y.orange == z.orange));
testPrint("member 2 comparison",(y.apple == z.apple));
testPrint("memcmp() comparison", !memcmp(&y,&z,sizeof(y)));
return 0;
}
Q.E.D. -- memcmp() is asking for trouble, even on the same platform.
--
Paul Lutus
www.arachnoid.com
Helmut Leitner wrote in message <37786F93...@hls.via.at>...
Richard Heathfield
<VS_d3.97674$_m4.10...@news2.giganews.com>...
<snip>
Paul - you are twisting the sense of the thread right out of shape.
The original question was:
"Let's assume that a and b have the same basic data type
(e.g. int, long, float, double ...). On many platforms it is possible to
replace the comparisions a==b, a!=b by memcmp(&a,&b,sizeof(a))==0,
memcmp(&a,&b,sizeof(a)) - What are the conditions that this will not yield
the desired results?"
Now, there is no way that you can equate y.orange == z.orange with y == z
without twisting reality somewhat. (Comparison of structs using == is of
course not legal C.) And since by your definition y.orange is a float and
z.orange is a double, you are off-beam there too, because a float is not a
double.
You have set up a straw man and you are now giving him a good pasting. But
this does not contribute in any way to answering the original question.
It pains me to see a usually logically-minded person "losing it" in this
fashion. /Please/ read before you think before you post.
(This whole reply would have gone to email if only I had an email address
to send it to. I'm tempted to set one up for you myself.)
--
Richard Heathfield
The bug stops here.
Paul Mesken
Kirby) wrote:
>In article <377b53ef...@news.euronet.nl>
> usu...@euronet.nl "Paul Mesken" writes:
>
>>On Mon, 28 Jun 1999 10:56:20 +0200, Helmut Leitner
>><lei...@hls.via.at> wrote:
>>
>>>Let's assume that a and b have the same basic data type
>>>(e.g. int, long, float, double ...).
>>>
>>>On many platforms it is possible to replace the
>>>comparisions
>>> a==b
>>> a!=b
>>>by
>>> memcmp(&a,&b,sizeof(a))==0
>>> memcmp(&a,&b,sizeof(a))
>>>
>>If a and b are of the same basic data type then you wouldn't do this.
>>It's ugly and probably slower. Besides: what if a and/or b have the
>>storage class specifier "register"? Then it is illegal to use the
>>address-of operator on them.
>
>The simple fix for that is to remove the register specifier. If you
>are writing the function containing the memcmpycall you should have
>control of the local variables in the function.
If you would want to do that, sure. But the question was about how
equal the memcmp version was to the equality operator version with a
and b being of the same basic data type.
I've seen interesting incompatibilities posted which I didn't think of
myself (how a pointer is stored, the floats (I never do floats) and
particular bit representation schemes for negative numbers) but mine
is the only one that results in an error :-)
Helmut Leitner
Lawrence Kirby wrote:
>
> In article <377738B4...@hls.via.at>
> lei...@hls.via.at "Helmut Leitner" writes:
>
> >Let's assume that a and b have the same basic data type
> >(e.g. int, long, float, double ...).
> >
> >On many platforms it is possible to replace the
> >comparisions
> > a==b
> > a!=b
> >by
> > memcmp(&a,&b,sizeof(a))==0
> > memcmp(&a,&b,sizeof(a))
> >
> >What are the conditions that this will not yield the
> >desired results?
>
> When different bit patterns represent the same value or at least
> values that compare equal. There are various reasons why this might
> happen.
>
> Firstly any basic type except unsigned char can have "holes" or unused
> bits that don't contribute to the value.
That's what I try to *really* understand.
At the moment (with your help and the other's contributions)
I see five different problems.
A. Clearing the structures including all bits and bytes that
may not be directly used for component content.
Solving this problem would result in a
StructClear(void *p,size_t size);
My naive implementation for this was
memset(p,'\0',size);
Might it be possible that this does not reach all bits
in memory? Could a fp-only implementation (say 96 bit cpu)
use 64 mantissa-bits for char/int/long/... ?
So that the memset above would not delete all bits used
for fp data representation?
Might it be possible in such cases to switch to a different
basic data type for the clearing process?
Can such a data type be selected in a portable way?
B. Assignment to structure components without using
ambiguous bit representations.
Solving this problem would result in a set of
assignment-functions:
void IntSetVal(int *pi,int val)
{
if(val==0) {
*pi=0; /* to avoid the +0/-0 problem */
} else {
*pi=val;
}
}
void StrSizeSetVal(char *d,size_t size,char *s)
/* usable only for "flat" string components */
{
memset(d,'0',size);
strcpy(d,s); /* no safety intended */
}
void DoubleSetVal(double *pd,double val)
{
switch(fpclassify(val)) {
case FP_INFINITE:
*pd=INFINITE;
break;
case FP_NAN:
*pd=NAN;
break;
case FP_ZERO:
*pd=0.0;
break;
case FP_SUBNORMAL:
*pd=val; /* no clue, what to do here
break;
case FP_NORMAL: default:
*pd=val;
break;
}
}
and similar functions:
void LongSetVal(...)
void FloatSetVal(...)
....
This leaves the problem of ambiguous pointer representation
open. Although for some cases (DOS segmented pointer) it might
be easy to normalize the pointers, I don't know what problems
could arise on other platforms.
C. Comparing the data structures sa and sb without leaving
out bits that are used by some component data representation.
Solving this problem would result in a reliable
struct-memory-compare functions.
int StructCmp(void *psa,void *psb,size_t size)
{
int ret=memcmp(psa,psb,size);
if(ret==0) {
/* what code needed here ??? */
/* absurd, only to fill the void: */
while(size>sizeof(double) && ret==0) {
ret= (*(double *)psa != *(double *)psb)
size-=sizeof(double);
psa+=sizeof(double);
psb+=sizeof(double);
}
}
return(ret);
}
My naive implementation for this was
memcmp(psa,psb,sizeof(*psa));
D. Similar to C, the problem of getting at all bits that
carry component information e.g. for calulating a hash
value. Will be solved when C ist solved.
E. May the system touch/change unused padding bytes within
a structure at will?
> So these bits can differ (hence
> memcmp() will return non-zero) for values that compare equal.
>
> In 1's complement and sign-mangitde format integers 0 and -0 have
> different bit representations but compare equal.
I tried to account for this in the assignment function.
> In floating point formats such as IEEE-754 there can also be different
> representations for 0 and -0. I believe in some floating point
> formats there are a large number of representations for zero. Some
> floating point formats such as IEEE-754 also create the opposite
> problem, NaNs compare unquual to anything even other NaNs so it is possible
> for values with identical bit patterns to compare unequal.
I tried to simplify the problem by reducing it.
In a real system I woulkd not allow NaNs to creep in, so
this problem would not give me bad dreams.
> Pointers can have different representations for the same address (e.g.
> in segnemted archatectures like the 8086). They can also contain other
> information such as boundary information (these are sometimes called fat
> pointers). So pointers with different bit patterns can compare equal.
Has this to do with access rights?
Would stripping these "fat pointer bits" be possible?
Could we assume, that after
char PiStr[]="3.14159";
...
char *p=PiStr;
... /* maybe different module */
char *q=PiStr;
the pointers p and q have the same bit representation?
> Structures and unions can include padding bytes. Since padding does not
> contribute to the structure or union's value I don't see anything that
> prohibits this padding from changing arbitrarily. There can also be
> padding bits where bit-fields are involved.
I try to clear all these bits and bytes and hope/expect
that "the system" will not quietly change them.
Is this unreasonable?
> >Can someone give (an) implementation example(s), where
> >the reasons for this behaviour can be seen?
> >
> >The background is the wish of fast and easy comparison
> >of multicomponent structures (within a perfect hash system):
> >
> > typedef struct test {
> > char ...
> > int ...
> > float ...
> > ...
> > } TEST;
> >
> > TEST sa,sb;
> > memset(&sa,'\0',sizeof(TEST)); /* or TestClear(&sa); */
> > memset(&sb,'\0',sizeof(TEST)); /* or TestClear(&sb); */
> > ...
> > any standard component assignment. /* or TestSetComponent(&sa,comp) */
> > ...
> > memcmp(&sa,&sb,sizeof(TEST));
> >
> >Is it possible to construct such a general system to work
> >in a portable way on all platforms?
>
> No.
>
> >Would it be possible to construct an #if-expression
> >
> > #if (expression_memcmp_will_do_the_job)
> > TestEqu(psa,psb) (memcmp(psa,psb,sizeof(TEST))==0)
> > #else
> > (psa->comp1==psb->comp2 && psa->comp2==psb->comp2 && .... )
> > #endif
> >
> >to react to the different situations?
>
> Probably the simplest thing to do would be to veryify the platforms
> you are interested in yourself
No problem here. It is a question of portability.
> and define a macro you can test for
> those platforms which fit the bill. However there are lots of
> different ways to fail.
I'll try to understand as many of them as possible.
Alex...@scitex.com
Helmut Leitner <lei...@hls.via.at> wrote:
>
>
> Lawrence Kirby wrote:
> > >What are the conditions that this will not yield the
> > >desired results?
> >
> > When different bit patterns represent the same value or at least
> > values that compare equal. There are various reasons why this might
> > happen.
> >
> > Firstly any basic type except unsigned char can have "holes" or
unused
> > bits that don't contribute to the value.
>
> That's what I try to *really* understand.
> At the moment (with your help and the other's contributions)
> I see five different problems.
>
> A. Clearing the structures including all bits and bytes that
> may not be directly used for component content.
>
> Solving this problem would result in a
> StructClear(void *p,size_t size);
> My naive implementation for this was
> memset(p,'\0',size);
>
> Might it be possible that this does not reach all bits
> in memory?
No, memset looks at an object as an array of unsigned chars;
since there are no holes or paddings in unsigned char, memset reaches
all bits.
The problem is - no data type except unsigned chars is guaranteed
not to have holes in its binary representation. So, for example,
int a,b;
a = 1;
b = 1;
-then memcmp(&a,&b,sizeof int) is not guaranteed to compare equal.
> C. Comparing the data structures sa and sb without leaving
> out bits that are used by some component data representation.
>
> Solving this problem would result in a reliable
> struct-memory-compare functions.
>
> int StructCmp(void *psa,void *psb,size_t size)
> {
> int ret=memcmp(psa,psb,size);
> if(ret==0) {
> /* what code needed here ??? */
> /* absurd, only to fill the void: */
> while(size>sizeof(double) && ret==0) {
> ret= (*(double *)psa != *(double *)psb)
> size-=sizeof(double);
> psa+=sizeof(double);
> psb+=sizeof(double);
> }
> }
> return(ret);
> }
>
> My naive implementation for this was
> memcmp(psa,psb,sizeof(*psa));
if memcmp returns 0, stuctures *are* equal; the problem is when it
returns non-zero - they still may be equal, except padding bits.
>
> D. Similar to C, the problem of getting at all bits that
> carry component information e.g. for calulating a hash
> value. Will be solved when C ist solved.
>
> E. May the system touch/change unused padding bytes within
> a structure at will?
Nothing forbids it.
No.
> > Probably the simplest thing to do would be to veryify the platforms
> > you are interested in yourself
>
> No problem here. It is a question of portability.
>
> > and define a macro you can test for
> > those platforms which fit the bill. However there are lots of
> > different ways to fail.
>
> I'll try to understand as many of them as possible.
The worst possible problem is padding bytes in basic types;
bitfields also don't fit your approach. You may zero all bits
of your structure/object prior to assignment - but that doesn't buy
you much, since in case of holes in type representation you may (and
probably shall) receive padding from the rvalue.
--
Regards,
Alex Krol
Disclaimer: I'm not speaking for Scitex Corporation Ltd
raw...@my-deja.com
FigBug <rra...@csc.UVic.CA> wrote:
>
> The point I was attemping to make was, that the following is useful:
>
> int i;
> long int li;
>
> i = 1;
> li = 1;
>
> if (i == li) blaa();
>
> and the following won't do anything usefull:
>
> float f;
> double d;
>
> f = 1.1;
> d = 1.1;
>
> if (f == d) blaa();
>
> above was usefull.
That certainly wasn't clear from your original post; it would have
helped to mention long and int. Despite taking part in a long thread
on == with floating point, I still don't even know for sure whether
double a,b;
a=1.1;
b=a;
implies that a==b afterward, let alone declaring a as float and
leaving b as double. But I am certain that memcmp could
only be worse.
--
MJSR
Szu-Wen Huang
[...]
: At the moment (with your help and the other's contributions)
Wouldn't the solution to these five problems outweigh the cost
of just writing a function to compare the two structures? If
I was maintaining this program, I'd probably find the mechanism
surprising.
Bill Godfrey
> Sure. Recall the strange segment:offset scheme of addressing
> on the 80x86 real mode, where the actual address is computed
> as (segment * 16 + offset). Thus, many segment:offset pairs
> actually compute to the same address, and the equality operator
> for pointers must handle these. Typically, they normalize the
> pointer before comparison.
Not necessarily. Under 8086, all "chunks" of memory have to sit within a
64k segment.
Imagine an arbitary array of 10 ints, at 0x1234:0x0004. When moving a pointer
about this array, only the offset needs changing. a[8] can be found at
0x1234:0x0014 (assuming 2 byte ints).
It's convient to calcuate the offset part and leave the segment well alone.
Later on, somehow the pointer 0x1233:0x0024 came along, and the code compared
== this pointer with a[8]. Using a simple bit compare, a mis-match would
be reported, even though it points to the same adress.
But wait! How did we get a pointer with value 0x1233:0x0024 in the first
place?
Underflowing or overflowing an array subscript? Bzzz. Undefined behaviour.
Pointer arthmetic outside an object's bounds? Bzzz. Undefined behaviour.
(int*)(0x12330024) ? Implementation defined.
Point is, a compiler targeting 8086 can get away with not normalising a
pointer, so long as it does not do any normalising anywhere else.
(Documenting the effect of comparing casted pointers notwithstanding.)
If just pointer gets normalised, then all pointers have to be normalised.
Anyway, I may have missed a legal way to get two representations of a
single pointer under my scheme, so look for any follow-ups before responding.
Bill, normal.
Szu-Wen Huang
[...]
: But wait! How did we get a pointer with value 0x1233:0x0024 in the first
: place?
: Underflowing or overflowing an array subscript? Bzzz. Undefined behaviour.
: Pointer arthmetic outside an object's bounds? Bzzz. Undefined behaviour.
: (int*)(0x12330024) ? Implementation defined.
: Point is, a compiler targeting 8086 can get away with not normalising a
: pointer, so long as it does not do any normalising anywhere else.
: (Documenting the effect of comparing casted pointers notwithstanding.)
[...]
I'm a bit confused. Do you mean that you can implement an ANSI C
compiler for the 8086 without normalizing pointers before comparing
them? If so, I agree 100%.
On the other hand, if you mean that normalizing is atypical, then
note that your solution won't work on >64KB objects. If memory
serves (good chance it won't), they're accessed with "huge"
pointers, and can cross segments.
Lawrence Kirby
usu...@euronet.nl "Paul Mesken" writes:
...
>I've seen interesting incompatibilities posted which I didn't think of
>myself (how a pointer is stored, the floats (I never do floats) and
>particular bit representation schemes for negative numbers) but mine
>is the only one that results in an error :-)
Good point. But that also makes it easy to spot and fix.
Helmut Leitner
"Dann Corbit" <dco...@solutionsiq.com> wrote:
> Quite right, a horrible gaffe (comparing doubles for equality), and
> indicates that the programmer is probably incompetent for numerical
work.
Be assured, that this thread is not about comparing floating point
numbers by memcmp. It is about hashing/comparing structures and
(not excluding floating point numbers striving for a general solution)
about all the problems coming from padding bits and bytes and
potential holes in the data representations of structure components.
--
Helmut Leitner lei...@hls.via.at
Graz, Austria www.hls-software.com
Helmut Leitner
Alex...@scitex.com wrote:
> > My naive implementation for this was
> > memset(p,'\0',size);
> >
> > Might it be possible that this does not reach all bits
> > in memory?
>
> No, memset looks at an object as an array of unsigned chars;
> since there are no holes or paddings in unsigned char, memset reaches
> all bits.
If this is true, then all my problems with StructCmp()
can be solved eventually. But I remember vaguely C
discussions about implementations on top of LISP or
on pure floating point machines, that might behave
differently. Could you quote the standard?
> ...
> The problem is - no data type except unsigned chars is guaranteed
> not to have holes in its binary representation. So, for example,
> int a,b;
> a = 1;
> b = 1;
> -then memcmp(&a,&b,sizeof int) is not guaranteed to compare equal.
But we could construct a
IntSetVal(int *pi,int val)
{
statuc char int_bits_of_rep[sizeof(int)]= { ... };
if(val==0) {
*pi=0; /* +0/-0 problem */
} else {
*pi=val;
}
MemAnd(pi,int_bits_of_rep,sizeof(int));
}
that would clear any available holes in the int
data representation.
> if memcmp returns 0, stuctures *are* equal; the problem is when it
> returns non-zero - they still may be equal, except padding bits.
If we can reach any padding bits and bytes, then we can also
clear them.
> > D. Similar to C, the problem of getting at all bits that
> > carry component information e.g. for calulating a hash
> > value. Will be solved when C ist solved.
> >
> > E. May the system touch/change unused padding bytes within
> > a structure at will?
>
> Nothing forbids it.
>
I know. But I would trust Occom's razor on this point.
> > Could we assume, that after
> > char PiStr[]="3.14159";
> > ...
> > char *p=PiStr;
> > ... /* maybe different module */
> > char *q=PiStr;
> > the pointers p and q have the same bit representation?
>
> No.
>
First, why not?
Second: In hashing structures it would not make much sense
to use "deep" structures for string content. If such pointers
would point to a fixed set of constant strings, they were
better replaced by enums.
> The worst possible problem is padding bytes in basic types;
> bitfields also don't fit your approach. You may zero all bits
> of your structure/object prior to assignment - but that doesn't buy
> you much, since in case of holes in type representation you may (and
> probably shall) receive padding from the rvalue.
Yes, bitfields would have to be isolated into substructures
and equipped with separate assignment functions.
--
Helmut Leitner lei...@hls.via.at
Graz, Austria www.hls-software.com
Alex...@scitex.com
Helmut Leitner <lei...@hls.via.at> wrote:
> In article <7laobh$imb$1...@nnrp1.deja.com>,
> Alex...@scitex.com wrote:
> > > memset(p,'\0',size);
> > >
> > > Might it be possible that this does not reach all bits
> > > in memory?
> >
> > No, memset looks at an object as an array of unsigned chars;
> > since there are no holes or paddings in unsigned char, memset
reaches
> > all bits.
>
> can be solved eventually. But I remember vaguely C
> discussions about implementations on top of LISP or
> on pure floating point machines, that might behave
> differently. Could you quote the standard?
At the moment I have at hand only C9X draft, but in this aspect it
doesn't differs from C89. So,
6.2.6.1 [#3] Values stored in object of type unsigned char shall be
represented using a pure binary notation
(C89 states the same)
and, as a consequence of this statement and a definition for pure
binary notation, uchar consists of CHAR_BIT bits and represents values
from 0 to 2^^CHAR_BIT-1. No place for padding or holes.
> > ...
> > The problem is - no data type except unsigned chars is
guaranteed
> > not to have holes in its binary representation. So, for example,
> > int a,b;
> > a = 1;
> > b = 1;
> > -then memcmp(&a,&b,sizeof int) is not guaranteed to compare equal.
>
> But we could construct a
>
> IntSetVal(int *pi,int val)
> {
> statuc char int_bits_of_rep[sizeof(int)]= { ... };
> if(val==0) {
> *pi=0; /* +0/-0 problem */
> } else {
> *pi=val;
> }
> MemAnd(pi,int_bits_of_rep,sizeof(int));
> }
>
> that would clear any available holes in the int
> data representation.
>
> > if memcmp returns 0, stuctures *are* equal; the problem is when
it
> > returns non-zero - they still may be equal, except padding bits.
>
> If we can reach any padding bits and bytes, then we can also
> clear them.
Well, it is possible - you have to initialise template for a
appropriate data type with all_zero padding bits and all_one significant
ones. But I'd be damned if I know how to do this portably.
> > > D. Similar to C, the problem of getting at all bits that
> > > carry component information e.g. for calulating a hash
> > > value. Will be solved when C ist solved.
> > >
> > > E. May the system touch/change unused padding bytes within
> > > a structure at will?
> >
> > Nothing forbids it.
> >
>
> I know. But I would trust Occom's razor on this point.
An extremely optimistic perception of fellow human beings :-)
What if some compiler writer doesn't follow Occam's principle?
>
> > > Could we assume, that after
> > > char PiStr[]="3.14159";
> > > ...
> > > char *p=PiStr;
> > > ... /* maybe different module */
> > > char *q=PiStr;
> > > the pointers p and q have the same bit representation?
> >
> > No.
> >
>
> First, why not?
a) Possible padding bits;
b) Segment:offset architectures.
> Second: In hashing structures it would not make much sense
> to use "deep" structures for string content. If such pointers
> would point to a fixed set of constant strings, they were
> better replaced by enums.
>
> > The worst possible problem is padding bytes in basic types;
> > bitfields also don't fit your approach. You may zero all bits
> > of your structure/object prior to assignment - but that doesn't buy
> > you much, since in case of holes in type representation you may (and
> > probably shall) receive padding from the rvalue.
>
> Yes, bitfields would have to be isolated into substructures
> and equipped with separate assignment functions.
Dann Corbit
news:7ld65a$e30$1...@nnrp1.deja.com...
> In article <T6Vd3.450$6n6.8084@client>,
> "Dann Corbit" <dco...@solutionsiq.com> wrote:
> > Quite right, a horrible gaffe (comparing doubles for equality), and
> > indicates that the programmer is probably incompetent for numerical
> work.
>
> Be assured, that this thread is not about comparing floating point
> numbers by memcmp. It is about hashing/comparing structures and
> (not excluding floating point numbers striving for a general solution)
> about all the problems coming from padding bits and bytes and
> potential holes in the data representations of structure components.
floats for equality the same way that you would compare integers. This is
wrong. Neither was I talking about comparing floating point numbers with
memcmp(). If you see something like this:
float a;
float b;
double c;
double d;
/* intervening stuff... */
if (a == b) foo(); else bar();
if (c == d) bar(); else foo();
It is a sure indication that the programmer does not understand floating
point. I have seen it *even* in Numerical Analysis textbooks, which only
goes to show that ignorance is widespread.
In other words, the part (a!=b) is dead wrong to begin with. Do you catch
my drift?
Helmut Leitner
> : I see five different problems.
>
> Wouldn't the solution to these five problems outweigh the cost
> of just writing a function to compare the two structures? If
> I was maintaining this program, I'd probably find the mechanism
> surprising.
>
I see "compare" as the smaller brother of "hash".
Both have to access all data bits and avoid all
padding bits to work.
You can write individual functions for the "compare",
but you still have all the same problems regarding
padding bits if you want to calculate a hash function.
--
Helmut Leitner lei...@hls.via.at
Graz, Austria www.hls-software.com
Helmut Leitner
"Dann Corbit" <dco...@solutionsiq.com> wrote:
> > Be assured, that this thread is not about comparing floating point
> > numbers by memcmp. It is about hashing/comparing structures and
> > (not excluding floating point numbers striving for a general
solution)
> > about all the problems coming from padding bits and bytes and
> > potential holes in the data representations of structure components.
> I was addressing a different issue. Some people think that you can
compare
> floats for equality the same way that you would compare integers.
This is
> wrong. Neither was I talking about comparing floating point numbers
with
> memcmp(). If you see something like this:
>
> float a;
> float b;
>
> double c;
> double d;
> /* intervening stuff... */
>
> if (a == b) foo(); else bar();
> if (c == d) bar(); else foo();
>
> It is a sure indication that the programmer does not understand
floating
> point. I have seen it *even* in Numerical Analysis textbooks,
I can hardly believe this.
> which only
> goes to show that ignorance is widespread.
>
> In other words, the part (a!=b) is dead wrong to begin with. Do you
catch
> my drift?
Ok, I see.
But I don't see what this has to do with double/float.
"a=b" or "a!=b" is wrong anyway.
"a=c" seem even "wronger", if this were possible.
The only answer I see is to implement
functions like
int DoubleEqu(double x,double y);
int FloatEqu(float x,float y);
int DoubleEquMantBitcount(double x,double y,int count);
int FloatEquMantBitcount(float x,float y,int count);
and to compare on the smaller precision level:
if(DoubleEqu(a,b)) ...
if(FloatEqu(a,c)) ...
if(FloatEqu(a,d)) ...
if(FloatEqu(c,d)) ...
...
I never understood why there is no proposed
implementation for such functions in the FAQ,
no proposal for the implicit use of such functions
in the C standard (for == and !=).
Helmut Leitner
Alex...@scitex.com wrote:
> > If this is true, then all my problems with StructCmp()
> > can be solved eventually. But I remember vaguely C
> > discussions about implementations on top of LISP or
> > on pure floating point machines, that might behave
> > differently. Could you quote the standard?
>
> At the moment I have at hand only C9X draft, but in this aspect it
> doesn't differs from C89. So,
> 6.2.6.1 [#3] Values stored in object of type unsigned char shall be
> represented using a pure binary notation
> (C89 states the same)
> and, as a consequence of this statement and a definition for pure
> binary notation, uchar consists of CHAR_BIT bits and represents values
> from 0 to 2^^CHAR_BIT-1. No place for padding or holes.
I found this (also in the C9X draft) but was not sure,
whether this guarantees access to any padding bits and bytes
of any other data type.
> > > ...
> > > The problem is - no data type except unsigned chars is
> guaranteed
> > > not to have holes in its binary representation. So, for example,
> > > int a,b;
> > > a = 1;
> > > b = 1;
> > > -then memcmp(&a,&b,sizeof int) is not guaranteed to compare equal.
> >
> > But we could construct a
> >
> > IntSetVal(int *pi,int val)
> > {
> > statuc char int_bits_of_rep[sizeof(int)]= { ... };
> > if(val==0) {
> > *pi=0; /* +0/-0 problem */
> > } else {
> > *pi=val;
> > }
> > MemAnd(pi,int_bits_of_rep,sizeof(int));
> > }
> >
> > that would clear any available holes in the int
> > data representation.
> >
> > > if memcmp returns 0, stuctures *are* equal; the problem is when
> it
> > > returns non-zero - they still may be equal, except padding bits.
> >
> > If we can reach any padding bits and bytes, then we can also
> > clear them.
>
> Well, it is possible - you have to initialise template for a
> appropriate data type with all_zero padding bits and all_one significant
> ones. But I'd be damned if I know how to do this portably.
For all integer data types it should be easy. E.g. something like
unsigned char IntDataBits[sizeof(int)];
void IntDataBitsInit(void)
{
int bits=sizeof(int)*CHAR_BIT;
int val_ref=314;
int i;
MemClear(IntDataBits,sizeof(IntDataBits));
for(i=0; i<bits; i++) {
val=val_ref;
PtrSetBit((unsigned char *)&val,i);
if(val!=val_ref) {
PtrSetBit(IntDataBits,i);
}
}
}
For floating point types it should be possible, but
one has to avoid pitfalls like producing NaNs that might
compare equal ...
At the moment I have no clue about pointer types
(as I said, they are not really useful in the context at hand)
Richard Heathfield
<7lf57v$74p$1...@nnrp1.deja.com>...
<snip>
> The only answer I see is to implement
> functions like
>
> int DoubleEqu(double x,double y);
> int FloatEqu(float x,float y);
> int DoubleEquMantBitcount(double x,double y,int count);
> int FloatEquMantBitcount(float x,float y,int count);
>
> and to compare on the smaller precision level:
>
> if(DoubleEqu(a,b)) ...
> if(FloatEqu(a,c)) ...
> if(FloatEqu(a,d)) ...
> if(FloatEqu(c,d)) ...
> ...
>
> I never understood why there is no proposed
> implementation for such functions in the FAQ,
> no proposal for the implicit use of such functions
> in the C standard (for == and !=).
>
Probably for the same reason that many "obvious" functions are missing from
C - such functions a) are trivial to write and b) would either not be
sufficiently general in usefulness to merit inclusion in the library, or
would be too general to be useful!
For example:
if(DoubleEqu(a,b))
is not very helpful. How equal is equal? Within +/- 0.000001 of each other?
0.00000000001? Or perhaps +/- 0.0001%? If so, how would you calculate the
percentage? a * 100 / b? ((a - b) * 100) / b? Or what if the user wanted to
compare to 6 significant figures? Or 7?
Tricky to design one easy-to-use function that copes elegantly with all
these possibilities and yet handles all comparisons of all possible float
(or double) values correctly.
It's simpler to just let the user-programmer write his own functions to do
this. And in fact that's precisely what I've had to do on several occasions
in the past, for various different clients.
Dik T. Winter
> float a;
> float b;
>
> double c;
> double d;
>
> if (c == d) bar(); else foo();
>
> It is a sure indication that the programmer does not understand floating
> point.
Tsk, tsk. A bit harsh Dann. I think I *do* understand floating point ;-).
There are places where exact equality is just what is required.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Helmut Leitner
Perhaps taking the larger (fabs) one as the measure.
> Or what if the user wanted to
> compare to 6 significant figures? Or 7?
Then he will have to take
DoubleEquSigDigits(x,y,6);
DoubleEquSigDigits(x,y,7);
and if wants to compare to two decimal digits
DoubleEquDecDigits(x,y,2);
And don't tell me all this is trivial.
> Tricky to design one easy-to-use function that copes elegantly with all
> these possibilities
Who says that it must be one function.
> and yet handles all comparisons of all possible float
> (or double) values correctly.
>
> It's simpler to just let the user-programmer write his own functions to do
> this.
Sure, it's a problem no one cares about. Which seems
to be not very productive from an overall point of view.
> And in fact that's precisely what I've had to do on several occasions
> in the past, for various different clients.
What I'm talking about is solving an old problem (x==y).
If it can be done in one function, fine.
If it can't be done in less than a 20 function API, fine too.
The complete API itself would document the depth and
all the variations of the problem.
Helmut Leitner
"Kevin D. Quitt" wrote:
>
> On Thu, 01 Jul 1999 08:55:05 +0200, Helmut Leitner <lei...@hls.via.at> wrote:
> >I found this (also in the C9X draft) but was not sure,
> >whether this guarantees access to any padding bits and bytes
> >of any other data type.
>
> It doesn't matter if you can zero all the holes. There is no guarantee that the
> bits in the holes are going to remain constant.
I know. But there is also no good reason for them to change.
> This is an artificial
> discussion in a sense, as I can't imagine a machine that really does this,
Yes, It is.
> but
> imagine that the holes are filled with bits from the clock. Each time you
> examine them, the bits in the holes can be different.
>
> Likewise, you can fill the holes in a struct, but there is no guarantee that the
> values in the padding will remain constant.
Lets assume that there were a good reason for a compiler to
change padding bits or hole bits quietly (and outside of a
component assignment process).
typedef struct test {
type1 x1; /* there is padding */
......... /* there are holes */
} TEST;
Now we "repack" it:
typedef struct test_rp {
union {
TEST t;
unsigned char ucbuf[sizeof(TEST)];
} u;
} TEST_RP;
Now he can't do it anymore, because he would risk quietly
changing value bits of ucbuf. But only during assigments does
can he know how the union is used...
So it doesn't make sense to think about a compiler using
padding bits and bytes or holes.
IMO it is a purely theoretical question, as long as there is no
single implementer standing up and telling us that he uses
paddings/holes and tells us about its usefulness.
Christian Bau
<lei...@hls.via.at> wrote:
> Lets assume that there were a good reason for a compiler to
> change padding bits or hole bits quietly (and outside of a
> component assignment process).
>
> typedef struct test {
> type1 x1; /* there is padding */
> ......... /* there are holes */
> } TEST;
>
> Now we "repack" it:
>
> typedef struct test_rp {
> union {
> TEST t;
> unsigned char ucbuf[sizeof(TEST)];
> } u;
> } TEST_RP;
>
> Now he can't do it anymore, because he would risk quietly
> changing value bits of ucbuf. But only during assigments does
> can he know how the union is used...
>
> So it doesn't make sense to think about a compiler using
> padding bits and bytes or holes.
>
> IMO it is a purely theoretical question, as long as there is no
> single implementer standing up and telling us that he uses
> paddings/holes and tells us about its usefulness.
Lets say you have a processor with a "load/store multiple register"
instruction, like PowerPC or 68000. And you have a struct
struct test {
long a;
long b;
long c;
short d;
long e;
} x, y;
You assign
x.a = y.a;
x.b = y.b;
x.c = y.c;
x.d = y.d;
That can be done on a 68000 with one "Load 4 registers" and one "Store
four registers" by a good optimising compiler. That will overwrite padding
between d and e. If you dont want to destroy the padding, you have to use
two more instructions.
Lawrence Kirby
Ke...@Quitt.net "Kevin D. Quitt" writes:
>On Thu, 01 Jul 1999 08:55:05 +0200, Helmut Leitner <lei...@hls.via.at> wrote:
>>I found this (also in the C9X draft) but was not sure,
>>whether this guarantees access to any padding bits and bytes
>>of any other data type.
>
>It doesn't matter if you can zero all the holes. There is no guarantee that the
>bits in the holes are going to remain constant.
I'm not entirely convinced about that. Consider that you can access anu object
as an array of unsigned char. Each unsigned char is an object in its
own right and, except through some mechanism involving volatile or undefined
behaviour, the value of an object cannot change except through a side-effect
visible in the abstract machine.
> This is an artificial
>discussion in a sense, as I can't imagine a machine that really does this, but
>imagine that the holes are filled with bits from the clock. Each time you
>examine them, the bits in the holes can be different.
That wouldn't be valid implementation.
>Likewise, you can fill the holes in a struct, but there is no guarantee that the
>values in the padding will remain constant.
In fact the only things I can think of that might legitimately change
padding bytes are structure assignment and possibly library functions that
modify a structure (e.g. mktime() ). When you modify a structure member you
are modifying an object through an lvalue of the member type. The parent
structure is of little concern once the member object has been located.
Modification of an object can't modify memory that isn't part of that object.
So modifying a structure member can't modify bytes that are not part of that
structure member.
A trickier question is whether modifying a bit-field can modify padding
bits in the allocation unit used for the bit-field. I suspect not
although I could imagine a compiler optimiser doing this to produce more
efficient code (e.g. by leaving out some masking operations).
Lawrence Kirby
Ke...@Quitt.net "Kevin D. Quitt" writes:
>On Tue, 29 Jun 99 20:51:17 , Bill Godfrey <bill-g...@usa.net> wrote:
>>Imagine an arbitary array of 10 ints, at 0x1234:0x0004. When moving a pointer
>>about this array, only the offset needs changing.
>
>This may be the case, but there is no guarantee that only the offset will be
>changed. Pointers may be normalized or denormalized by library routines or
>generated code; nothing prevents this.
>
>
>>But wait! How did we get a pointer with value 0x1233:0x0024 in the first
>>place?
>
>It doesn't matter - you can't guarantee one won't be created.
You can if it messes up a legitimate comparison operation in another part
of the program. An implementation must be consistent in either maintaining
a normalised form for pointers or generating code for comparisons that
doesn't depend on a normalised form (although localised optimisations
may apply).
Lawrence Kirby
lei...@hls.via.at "Helmut Leitner" writes:
>In article <7laobh$imb$1...@nnrp1.deja.com>,
> Alex...@scitex.com wrote:
>> > My naive implementation for this was
>> > memset(p,'\0',size);
>> >
>> > Might it be possible that this does not reach all bits
>> > in memory?
>>
>> No, memset looks at an object as an array of unsigned chars;
>> since there are no holes or paddings in unsigned char, memset reaches
>> all bits.
>
>If this is true, then all my problems with StructCmp()
>can be solved eventually.
I doubt it, at least not in a way that is ultimately simpler than
comparing the structure members individually.
Consider another problem - a structure that contains arrays of char
holding strings. Any data in the array after the null will have no
effect on the string comparison but it will affect a memcmp()
comparison unless you ensure that all trailing bytes are set to
zero or another consistent value. This implies either knowledge of
the structure dataformat in the comparison routine or overhead in
anything that manipulates the array contents. The latter option can
easily be mishandled producing difficult to track down bugs.
>But I remember vaguely C
>discussions about implementations on top of LISP or
>on pure floating point machines, that might behave
>differently. Could you quote the standard?
The current standard is a bit vague in this respect. However functions
like memcpy() are defined to copy arrays of unsigned characters. For them
yo work properly (i.e. be able to copy objects of any type) all data
within any type must be represented when viewed as an array of unsigned
char. C9X will make such guarantees explicit.
In principle a C implementation could be built on top of something
else such as the examples you give. These underlying "architectures"
could use extra bits and datastructures that are invisible to the C
program. However since they are invisible to the C program they are
irrelevant. In particular such things cannot contribute to any object's
value.
>> ...
>> The problem is - no data type except unsigned chars is guaranteed
>> not to have holes in its binary representation. So, for example,
>> int a,b;
>> a = 1;
>> b = 1;
>> -then memcmp(&a,&b,sizeof int) is not guaranteed to compare equal.
>
>But we could construct a
>
> IntSetVal(int *pi,int val)
> {
> statuc char int_bits_of_rep[sizeof(int)]= { ... };
> if(val==0) {
> *pi=0; /* +0/-0 problem */
> } else {
> *pi=val;
> }
> MemAnd(pi,int_bits_of_rep,sizeof(int));
> }
>
>that would clear any available holes in the int
>data representation.
What you're saying is that you can force a canonical representation
of any value that an object can store. Possibly bu such code would be
highly platform-specific and it would still probably need to be done
per structure type. A better approach would be to write a hashing function
for each structure type. This would be far more maintainable and
portable.
Helmut Leitner
Lawrence Kirby wrote:
>
> In article <7ldc42$goi$1...@nnrp1.deja.com>
> lei...@hls.via.at "Helmut Leitner" writes:
>
> >In article <7laobh$imb$1...@nnrp1.deja.com>,
> > Alex...@scitex.com wrote:
> >> > My naive implementation for this was
> >> > memset(p,'\0',size);
> >> >
> >> > Might it be possible that this does not reach all bits
> >> > in memory?
> >>
> >> No, memset looks at an object as an array of unsigned chars;
> >> since there are no holes or paddings in unsigned char, memset reaches
> >> all bits.
> >
> >If this is true, then all my problems with StructCmp()
> >can be solved eventually.
>
> I doubt it, at least not in a way that is ultimately simpler than
> comparing the structure members individually.
Well, one has to try. At first it seemed impossible,
now it seems possible (at least for flat structures).
> Consider another problem - a structure that contains arrays of char
> holding strings. Any data in the array after the null will have no
> effect on the string comparison but it will affect a memcmp()
> comparison unless you ensure that all trailing bytes are set to
> zero or another consistent value. This implies either knowledge of
> the structure dataformat in the comparison routine or overhead in
> anything that manipulates the array contents.
Little overhead during the assignment (put '\0' after the
end of the string to fill the complete array).
StrCpySizeFillZero(d,p,sizeof(array))
No overhead for the calling interface, because the size of
the array should already be included to protect the other
components of the structure.
> The latter option can
> easily be mishandled producing difficult to track down bugs.
I don't understand this argument.
> >But I remember vaguely C
> >discussions about implementations on top of LISP or
> >on pure floating point machines, that might behave
> >differently. Could you quote the standard?
>
> The current standard is a bit vague in this respect. However functions
> like memcpy() are defined to copy arrays of unsigned characters. For them
> yo work properly (i.e. be able to copy objects of any type) all data
> within any type must be represented when viewed as an array of unsigned
> char. C9X will make such guarantees explicit.
Good news!
> In principle a C implementation could be built on top of something
> else such as the examples you give. These underlying "architectures"
> could use extra bits and datastructures that are invisible to the C
> program. However since they are invisible to the C program they are
> irrelevant. In particular such things cannot contribute to any object's
> value.
>
> >> ...
> >> The problem is - no data type except unsigned chars is guaranteed
> >> not to have holes in its binary representation. So, for example,
> >> int a,b;
> >> a = 1;
> >> b = 1;
> >> -then memcmp(&a,&b,sizeof int) is not guaranteed to compare equal.
> >
> >But we could construct a
> >
> > IntSetVal(int *pi,int val)
> > {
> > statuc char int_bits_of_rep[sizeof(int)]= { ... };
> > if(val==0) {
> > *pi=0; /* +0/-0 problem */
> > } else {
> > *pi=val;
> > }
> > MemAnd(pi,int_bits_of_rep,sizeof(int));
> > }
> >
> >that would clear any available holes in the int
> >data representation.
>
> What you're saying is that you can force a canonical representation
> of any value that an object can store. Possibly bu such code would be
> highly platform-specific
I don't see this.
> and it would still probably need to be done
> per structure type.
Why do you think so?
> A better approach would be to write a hashing function
> for each structure type.
If it can't be made portable and independent
your right.
> This would be far more maintainable and
> portable.
If it can be made portable and structure independent,
then IMO your wrong.