473,842 Members | 1,945 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Making Fatal Hidden Assumptions

We often find hidden, and totally unnecessary, assumptions being
made in code. The following leans heavily on one particular
example, which happens to be in C. However similar things can (and
do) occur in any language.

These assumptions are generally made because of familiarity with
the language. As a non-code example, consider the idea that the
faulty code is written by blackguards bent on foulling the
language. The term blackguards is not in favor these days, and for
good reason. However, the older you are, the more likely you are
to have used it since childhood, and to use it again, barring
specific thought on the subject. The same type of thing applies to
writing code.

I hope, with this little monograph, to encourage people to examine
some hidden assumptions they are making in their code. As ever, in
dealing with C, the reference standard is the ISO C standard.
Versions can be found in text and pdf format, by searching for N869
and N1124. [1] The latter does not have a text version, but is
more up-to-date.

We will always have innocent appearing code with these kinds of
assumptions built-in. However it would be wise to annotate such
code to make the assumptions explicit, which can avoid a great deal
of agony when the code is reused under other systems.

In the following example, the code is as downloaded from the
referenced URL, and the comments are entirely mine, including the
'every 5' linenumber references.

/* Making fatal hidden assumptions */
/* Paul Hsiehs version of strlen.
http://www.azillionmonkeys.com/qed/asmexample.html

Some sneaky hidden assumptions here:
1. p = s - 1 is valid. Not guaranteed. Careless coding.
2. cast (int) p is meaningful. Not guaranteed.
3. Use of 2's complement arithmetic.
4. ints have no trap representations or hidden bits.
5. 4 == sizeof(int) && 8 == CHAR_BIT.
6. size_t is actually int.
7. sizeof(int) is a power of 2.
8. int alignment depends on a zeroed bit field.

Since strlen is normally supplied by the system, the system
designer can guarantee all but item 1. Otherwise this is
not portable. Item 1 can probably be beaten by suitable
code reorganization to avoid the initial p = s - 1. This
is a serious bug which, for example, can cause segfaults
on many systems. It is most likely to foul when (int)s
has the value 0, and is meaningful.

He fails to make the valid assumption: 1 == sizeof(char).
*/

#define hasNulByte(x) ((x - 0x01010101) & ~x & 0x80808080)
#define SW (sizeof (int) / sizeof (char))

int xstrlen (const char *s) {
const char *p; /* 5 */
int d;

p = s - 1;
do {
p++; /* 10 */
if ((((int) p) & (SW - 1)) == 0) {
do {
d = *((int *) p);
p += SW;
} while (!hasNulByte (d)); /* 15 */
p -= SW;
}
} while (*p != 0);
return p - s;
} /* 20 */

Let us start with line 1! The constants appear to require that
sizeof(int) be 4, and that CHAR_BIT be precisely 8. I haven't
really looked too closely, and it is possible that the ~x term
allows for larger sizeof(int), but nothing allows for larger
CHAR_BIT. A further hidden assumption is that there are no trap
values in the representation of an int. Its functioning is
doubtful when sizeof(int) is less that 4. At the least it will
force promotion to long, which will seriously affect the speed.

This is an ingenious and speedy way of detecting a zero byte within
an int, provided the preconditions are met. There is nothing wrong
with it, PROVIDED we know when it is valid.

In line 2 we have the confusing use of sizeof(char), which is 1 by
definition. This just serves to obscure the fact that SW is
actually sizeof(int) later. No hidden assumptions have been made
here, but the usage helps to conceal later assumptions.

Line 4. Since this is intended to replace the systems strlen()
function, it would seem advantageous to use the appropriate
signature for the function. In particular strlen returns a size_t,
not an int. size_t is always unsigned.

In line 8 we come to a biggie. The standard specifically does not
guarantee the action of a pointer below an object. The only real
purpose of this statement is to compensate for the initial
increment in line 10. This can be avoided by rearrangement of the
code, which will then let the routine function where the
assumptions are valid. This is the only real error in the code
that I see.

In line 11 we have several hidden assumptions. The first is that
the cast of a pointer to an int is valid. This is never
guaranteed. A pointer can be much larger than an int, and may have
all sorts of non-integer like information embedded, such as segment
id. If sizeof(int) is less than 4 the validity of this is even
less likely.

Then we come to the purpose of the statement, which is to discover
if the pointer is suitably aligned for an int. It does this by
bit-anding with SW-1, which is the concealed sizeof(int)-1. This
won't be very useful if sizeof(int) is, say, 3 or any other
non-poweroftwo. In addition, it assumes that an aligned pointer
will have those bits zero. While this last is very likely in
todays systems, it is still an assumption. The system designer is
entitled to assume this, but user code is not.

Line 13 again uses the unwarranted cast of a pointer to an int.
This enables the use of the already suspicious macro hasNulByte in
line 15.

If all these assumptions are correct, line 19 finally calculates a
pointer difference (which is valid, and of type size_t or ssize_t,
but will always fit into a size_t). It then does a concealed cast
of this into an int, which could cause undefined or implementation
defined behaviour if the value exceeds what will fit into an int.
This one is also unnecessary, since it is trivial to define the
return type as size_t and guarantee success.

I haven't even mentioned the assumption of 2's complement
arithmetic, which I believe to be embedded in the hasNulByte
macro. I haven't bothered to think this out.

Would you believe that so many hidden assumptions can be embedded
in such innocent looking code? The sneaky thing is that the code
appears trivially correct at first glance. This is the stuff that
Heisenbugs are made of. Yet use of such code is fairly safe if we
are aware of those hidden assumptions.

I have cross-posted this without setting follow-ups, because I
believe that discussion will be valid in all the newsgroups posted.

[1] The draft C standards can be found at:
<http://www.open-std.org/jtc1/sc22/wg14/www/docs/>

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell. org/google/>
Also see <http://www.safalra.com/special/googlegroupsrep ly/>

Mar 6 '06
351 13203

David Holland wrote:
On 2006-03-07, James Dow Allen <jd*********@ya hoo.com> wrote:
> [...] but I'm sincerely curious whether anyone knows of an *actual*
> environment where p == s will ever be false after (p = s-1; p++).


The problem is that evaluating s-1 might cause an underflow and a
trap, and then you won't even reach the comparison. You don't
necessarily have to dereference an invalid pointer to get a trap.

You might hit this behavior on any segmented architecture (e.g.,
80286, or 80386+ with segments on) ...


I'm certainly no x86 expert. Can you show or point to the output
of any C compiler which causes an "underflow trap" in this case?

At the risk of repetition, I'm *not* asking whether a past or future
compiler might or may trap (or trash my hard disk); I'd just be curious
to
see one (1) actual instance where the computation (without dereference)
p=s-1 causes a trap.

James

Mar 9 '06 #111
Andrew Reilly wrote:
.... snip ...
I reckon I'll just go with the undefined flow, in the interests of
efficient, clean code on the architectures that I target. I'll
make sure that I supply a document specifying how the compilers
must behave for all of the undefined behaviours that I'm relying
on, OK? I have no interest in trying to make my code work on
architectures for which they don't hold.


That's just fine with me, and is the attitude I wanted to trigger.
As long as you recognize and document those assumptions, all is
probably well. In the process you may well find you don't need at
least some of the assumptions, and improve your code portability
thereby.

In the original sample code, it is necessary to deduce when an
integer pointer can be used in order to achieve the goals of the
routine. Thus it is necessary to make some of those assumptions.
Once documented, people know when the code won't work.

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell. org/google/>
Also see <http://www.safalra.com/special/googlegroupsrep ly/>
Mar 9 '06 #112
msg wrote:
On the other hand, when Seymour Cray started his own company,
those machines where 2's complement.


The Cray blood-line starting at least with "Little Character"
(prototype for the 160) was 1's complement, implemented with
subtraction as the basis of arithmetic (the so-called 'adder
pyramid'). Even the CDC 3000 series which were mostly others'
designs retained 1's complement arithmetic. The 6000 and 7000
series PPUs were essentially 160s also. I should think it safe
to say one could find 1's complement in Cray designs from at
least 1957 through the early 1980s.


Please don't remove attributions for material you quote.

The reason to use a subtractor is that that guarantees than -0
never appears in the results. This allows using that value for
such things as traps, uninitialized, etc. It also simplifies
operand sign and zero detection. The same thing applies to decimal
machines using 9s complement, and I realized it too late to take
proper advantage in the firstpc, as shown on my website.

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell. org/google/>
Also see <http://www.safalra.com/special/googlegroupsrep ly/>
Mar 9 '06 #113
Al Balmer wrote:
Chris Torek <no****@torek.n et> wrote:
Richard Heathfield <in*****@invali d.invalid> wrote:
Keith Thompson said: Um, I always thought that "within" and "outside" were two
different things.

Ask Jack to lend you his bottle. You'll soon change your mind.


To clarify a bit ...

A mathematician named Klein
Thought the Moebius band was divine
Said he, "If you glue
The edges of two
You'll get a weird bottle like mine!"
:-)

(A Moebius band has only one side. It is a two-dimensional object
that exists only in a 3-dimensional [or higher] space. A Klein
bottle can only be made in a 4-dimensional [or higher] space, and
is a 3-D object with only one side. The concept can be carried on
indefinitely, but a Klein bottle is hard enough to contemplate
already.)


But that was Felix. Who's Jack?


Jack Klein, a noted contributor, especially in c.a.e.

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell. org/google/>
Also see <http://www.safalra.com/special/googlegroupsrep ly/>
Mar 9 '06 #114
"James Dow Allen" <jd*********@ya hoo.com> wrote:
David Holland wrote:
On 2006-03-07, James Dow Allen <jd*********@ya hoo.com> wrote:
> [...] but I'm sincerely curious whether anyone knows of an *actual*
> environment where p == s will ever be false after (p = s-1; p++).


The problem is that evaluating s-1 might cause an underflow and a
trap, and then you won't even reach the comparison. You don't
necessarily have to dereference an invalid pointer to get a trap.

You might hit this behavior on any segmented architecture (e.g.,
80286, or 80386+ with segments on) ...


I'm certainly no x86 expert. Can you show or point to the output
of any C compiler which causes an "underflow trap" in this case?

At the risk of repetition, I'm *not* asking whether a past or future
compiler might or may trap (or trash my hard disk); I'd just be curious
to
see one (1) actual instance where the computation (without dereference)
p=s-1 causes a trap.


I don't know of any case where an pet grizzly bear who escaped has eaten
anyone in the Netherlands, but I'm still not short-sighted enough to use
that as an argument to allow grizzly bears as pets.

Richard
Mar 9 '06 #115
Andrew Reilly <an************ *@areilly.bpc-users.org> wrote:
On Wed, 08 Mar 2006 13:14:39 -0800, Andrey Tarasevich wrote:
This is a perfectly reasonable approach for a higher level language.


C is not a higher-level language. It's a universal assembler. Pick
another one.


All that statement means is that the person who utters it knows
diddly-squat about either C _or_ assembler.

Richard
Mar 9 '06 #116
In article <pa************ *************** *@areilly.bpc-users.org>,
Andrew Reilly <an************ *@areilly.bpc-users.org> wrote:
On Thu, 09 Mar 2006 00:15:17 +0000, Christian Bau wrote:
I just tried the following program (CodeWarrior 10 on MacOS X):


Same for gcc4 on MacOS X. However this slight permutation of your
program (only the comparison line has changed):

#include <stdio.h>

#define SIZE (50*1000000L)
typedef struct {
char a [SIZE];
} bigstruct;

static bigstruct bigarray [8];

int main(void)
{
printf("%lx\n", (unsigned long) &bigarray [0]);
printf("%lx\n", (unsigned long) &bigarray [9]);
printf("%lx\n", (unsigned long) &bigarray [-1]);

if (&bigarray [-1] - & bigarray [0] < 0)
printf ("Everything is fine\n");
else
printf ("The C Standard is right: &bigarray [-1] is broken\n");

return 0;
}

produces:
3080
1ad2a500
fd054000
Everything is fine

So what we see is that (a) pointer comparisons use direct unsigned integer
comparison, instead of checking the sign of the pointer difference---since
pointer comparisons only make sense in the context of an indivdual object,
I'd argue that the compiler is doing the wrong thing here, and the
comparison should instead have been done in the context of a pointer
difference; and (b) your printf string about "&bigarray[-1] is broken" is
wrong, since that's not what the code showed at all. What it showed is
that &bigarray[-1] could be formed, that &bigarray[0] was one element to
the right of it, and that hell did not freeze over (nor was any trap
taken), since you did not attempt to access any memory there.


We didn't see anything. The code involved undefined behavior.

Now try the same with array indices -2, -3, -4 etc. and tell us when is
the first time that the program says your code is broken.

Or try this one on a 32 bit PowerPC or x86 system:

double* p;
double* q;

q = p + 0x2000000;
if (p == q)
printf ("It is broken!!!");
if (q - p == 0)
printf ("It is broken!!!");
Mar 9 '06 #117
In article <44************ ***@yahoo.com> cb********@main eline.net writes:
....
The reason to use a subtractor is that that guarantees than -0
never appears in the results. This allows using that value for
such things as traps, uninitialized, etc.


This was however not done on any of the 1's complement machines I have
worked with. The +0 preferent machines (CDC) just did not generate it
in general. The -0 preferent machines I used (Electrologica) in general
did not generate +0. Bit the number not generated was not handled as
special in any way.

I have seen only one machine that used some particular bit pattern in
integers in a special way. The Gould. 2's complement but what would
now be regarded as the most negative bit pattern was a trap representation
on the Gould.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Mar 9 '06 #118

Andrew Reilly wrote:
On Wed, 08 Mar 2006 18:07:45 -0700, Al Balmer wrote:
On Thu, 09 Mar 2006 09:13:24 +1100, Andrew Reilly
<an************ *@areilly.bpc-users.org> wrote:
C is not a higher-level language. It's a universal assembler. Pick
another one.
Nice parrot. I think the original author of that phrase meant it as a
joke.


Most jokes contain at least a kernel of truth.


Funny, I always called it a glorified assembler.

It fills a nitch that few true high level languages can.
I spent 25 years writing assembler. C is a higher-level language.
Yeah, me to. Still do, regularly, on processors that will never have a C
compiler. C is as close to a universal assembler as we've got at the
moment. It doesn't stick it's neck out too far, although a more
deliberately designed universal assembler would be a really good thing.
(It's on my list of things to do...)


Would a better universal assembler be more like assembler or more like
high level languages? I really think C hit very close to the optimal
balance.

If you actually *want* a higher level language, there are better ones
to chose from than C.


Good programmers definitely have to be multilingual.
ed

Mar 9 '06 #119
"Ed Prochak" <ed*******@gmai l.com> writes:
Andrew Reilly wrote:

[...]
Yeah, me to. Still do, regularly, on processors that will never have a C
compiler. C is as close to a universal assembler as we've got at the
moment. It doesn't stick it's neck out too far, although a more
deliberately designed universal assembler would be a really good thing.
(It's on my list of things to do...)


Would a better universal assembler be more like assembler or more like
high level languages? I really think C hit very close to the optimal
balance.


Whether C is a "universal assembler" is an entirely separate question
from whether C is "good", or "better" than something else, or close to
some optimal balance.

As I understand the term, an assembly language is a symbolic language
in which the elements of the language map one-to-one (or nearly so)
onto machine-level instructions. Most assembly languages are, of
course, machine-specific, since they directly specify the actual
instructions. One could imagine a more generic assembler that uses
some kind of pseudo-instructions that can be translated more or less
one-to-one to actual machine instructions. C, though it's closer to
the machine than some languages, is not an assembler in this sense; in
a C program, you specify what you want the machine to do, not what
instructions it should use to do it.

<OT>Forth might be an interesting data point in this discussion, but
if you're going to go into that, please drop comp.lang.c from the
newsgroups.</OT>

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Mar 9 '06 #120

This thread has been closed and replies have been disabled. Please start a new discussion.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.