Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Warren W. Gay VE3WWG]

Markus Mottl wrote:
> In comp.lang.functional Joachim Durchholz <joachim_d@gmx.de> wrote:
> > Could you share a reference to a report?
> 
> Here is a somewhat longer treatment of the case:
> 
>   http://www.jerrypournelle.com/reports/jerryp/Yorktown.html
> 
> In short: a divide-by-zero in a database caused a Windows NT server to
> crash, paralyzing the whole computer network on the cruiser Yorktown
> for more than two hours.

IMHO, it seems to me that advantages of having compiler generated 
bounds checking and overflow checking code are too often 
dismissed by the C/C++ camp.

Just the other day, I came across a subtle C problem, that was
discovered when I ported the algorthm to Ada95. I checked the 
most recent version of SoX source, and the problem _still_
exists there, apparently still undiscovered.

Ada on the other hand, detected the problem very early 
in the porting development.

The following C snippet converts linear 16-bit 
signed sound samples to A-law compressed samples. The 
abbreviated code looks like this:

#define ACLIP 31744
...
unsigned char
st_linear_to_Alaw( sample )
short sample;
    {
    static const unsigned char exp_lut[128] = { ...snip... };
    int sign, exponent, mantissa;
    unsigned char Alawbyte;

    /* Get the sample into sign-magnitude. */
    sign = ((~sample) >> 8) & 0x80;		/* set aside the sign */
    if ( sign == 0 ) sample = -sample;		/* get magnitude */
    if ( sample > ACLIP ) sample = ACLIP;	/* clip the magnitude */
    ...

The logic is a bit twisted here because of the way the
sign bit is tested, but you should be able to see the
problem with a bit of effort.

The error occurs on the following line :

    if ( sign == 0 ) sample = -sample;		/* get magnitude */

Did anybody spot the problem?  I'm sure some did,
since I drew attentiont to it. While the logic is 
reversed in "(sign == 0)", the problem is this:

The statement sample = -sample is executed when the linear 
sample is negative, and _then_ the sample is clipped 
based on its _positive_ magnitude, in the next statement.

But what happens when the sample is -32768 ?

Testing this on Red Hat 7, under Linux and HPUX, the 
result of the test shows that sample = -sample when 
sample = -32768 is -32768 !  With this as the result, 
the next statement fails to carry out the clipping 
code: sample = ACLIP;

The end result?  A botched encoded sample. Something that
you probably would not hear with your ear. In practice
this only happens when your samples are maxing out on
the 16-bit range, which for recordings will likely result
in a lot of clipped (noisy) samples anyway.

So you might say, "so what?"

Two things:

1) The result is incorrect (that should be enough)

2) This is still a problem for good 16-bit samples 
   that are perhaps "processed" to use the maximum 
   dynamic range (they may have been 32-bit samples 
   before processed into 16-bit samples).

Ada picked this problem up right away, albeit at runtime.
When I saw the constraint error there, I immediately 
realized that I had overlooked this special case. This 
long time problem was obviously never detected by 
the C developers, and may now eventually get fixed 
as a result of this posting ;-)

I wonder how many other sound projects derived from this
same code, and possess the same bug? Windows CoolEdit?

Anyway, while sound samples don't paralyze ships, I felt 
that this is another example of how subtle errors like this
can go undetected in C/C++ code.  Ada on the other hand
was quick to point out this flaw. Kudos to GNAT. ;-)
-- 
Warren W. Gay VE3WWG
http://members.home.net/ve3wwg

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Ted Dennison]

In article <3B83F042.4CFB073D@home.com>, Warren W. Gay VE3WWG says...
>IMHO, it seems to me that advantages of having compiler generated 
>bounds checking and overflow checking code are too often 
>dismissed by the C/C++ camp.

Its a lot easier to dismiss, when you've never tasted its charms in the first
place. :-)

>Just the other day, I came across a subtle C problem, that was
>discovered when I ported the algorthm to Ada95. I checked the 
>most recent version of SoX source, and the problem _still_
>exists there, apparently still undiscovered.

Its truly *amazing* how many times I've heard that exact same story (although
the other language is not always C). I've even heard one person seriously
suggest that an Ada port may be a good idea for projects that have no intention
of using the Ada port, just to catch some more bugs. I think that's probably a
bit extreme though. :-)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
          home email - mailto:dennison@telepath.com

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Warren W. Gay VE3WWG]

Ted Dennison wrote:
> >Just the other day, I came across a subtle C problem, that was
> >discovered when I ported the algorthm to Ada95. I checked the
> >most recent version of SoX source, and the problem _still_
> >exists there, apparently still undiscovered.
> 
> Its truly *amazing* how many times I've heard that exact same story (although
> the other language is not always C). I've even heard one person seriously
> suggest that an Ada port may be a good idea for projects that have no intention
> of using the Ada port, just to catch some more bugs. I think that's probably a
> bit extreme though. :-)

Heh heh, an interesting idea ;-)
-- 
Warren W. Gay VE3WWG
http://members.home.net/ve3wwg

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Kaz Kylheku]

In article <3B83F042.4CFB073D@home.com>, Warren W. Gay VE3WWG wrote:
>#define ACLIP 31744
>...
>unsigned char
>st_linear_to_Alaw( sample )
>short sample;
>    {
>    static const unsigned char exp_lut[128] = { ...snip... };
>    int sign, exponent, mantissa;
>    unsigned char Alawbyte;
>
>    /* Get the sample into sign-magnitude. */
>    sign = ((~sample) >> 8) & 0x80;		/* set aside the sign */
>    if ( sign == 0 ) sample = -sample;		/* get magnitude */
>    if ( sample > ACLIP ) sample = ACLIP;	/* clip the magnitude */
>    ...

Even before seeing the body of the function, I wonder why it's using
old-style C. Even if there is a good reason for using old-style C,
why is it using a promotable type for a parameter? The use of a promotable
type means that if a correct function prototype is written for the
function, it will have to use the promoted type, that is to say:

	unsigned char st_linear_to_Alaw (int sample);

Lastly, why is the type short being used at all? The advantage of short
is that it may provide a compact representation for a large array of
integers, provided that a range no wider than -32767 to 32767 is required
(the minimum range required by ANSI/ISO C for the type short).

The way the sign is detected is completely braindamaged; it assumes
that signed short is 16 bits wide, so that shifting it 8 bits
to the right will cause the sign bit to land in position 7.
Also, shifting right a signed quantity whose sign bit is 1 is
implementation-defined; I think it's undefined in C99.

What is wrong with, say:

	sign = (sample >= 0);	/* 0 if negative */

Clearly, the programmer did not inspect that the function will produce
the correct output value for every input.  It was obviously not even
tested or inspected what happens in inputs representing interesting
partitions of the input space, such as -32768, -32767, 0 or 32767.

The program is probably not accompanied by test cases consisting of files
containing 16 bit linear samples and corresponding alaw files that are
known to be correct.

So we could say a number of things besides ``sox is written in the
wrong programming language''.

If this function is submitted for critique to comp.lang.c, the errors
in it will be shaken out in an instant, and a maximally portable version
will soon appear that will work on C implementations with unusual sizes
of integral types, CHAR_BIT other than 8, and sign-magnitude or ones'
complement representations for negative numbers. Try it!

Would you hire the programmer who wrote this function, to work with you
on a project in *any* programming language? 

If we are going to blame the programming language rather than the
programmer then let's do it right. If the programming language is at
fault, then it's because of the data representation. The program logic is
correct over abstract integers; it fails due to the machine-oriented data
represetation.   So the problem is that the language allows the programmer
to say ``use ony 16 bits and fail if the computation requires more''.
That in itself is an usafe feature, regardless of whether the overflow
is detected or not. Either way, the program fails to compute the result.

Although detection in Ada is superior to ignoring the error in C,
stopping the program on 16 bit overflow can still crash a rocket.

If I ported the essence of the algorithm to Common Lisp (for instance),
then it will just work. The additive inverse of  -32768 will be happily
computed as 32768.  The undisciplined programmer won't be seduced into
writing nonsense, such as artificially restricting the width of the
computation. The integer type tries to approximate mathematical integers
within the limitations of the machine resources.

(defconstant *alaw-clip* 42) ;; substitute actual value here

(defun st-linear-to-alaw (sample)
 (check-type sample integer)
 (let ((is-negative (< sample 0)))
  (setf sample (min (abs sample) *alaw-clip*))

   ;; rest of the algorithm with a-law table lookup, etc...

   ))

No bit manipulation tricks for detecting the sign, no 16 bit
representation braindamage. The sample parameter could be a bignum,
and it will work correctly. An alorithm can be described using pure,
mathematical integers, and then turned into code directly, without
worring about representation issues such as the limited range of
integers. Prevention of such issues is superior to detection.

So the bottom line is that whether you are programming in static
languages like C or Ada, you are metaphorically carving clay tablets
with with stone knives.  These languages trade reliability and clarity
for machine efficiency. Trivial differences among them are dwarfed by
the differences between them and a truly high level language.

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Dale Stanbrough]

Kaz Kylheku wrote:

> Even before seeing the body of the function, I wonder why it's using
> old-style C. Even if there is a good reason for using old-style C,
> why is it using a promotable type for a parameter? The use of a promotable
> type means that if a correct function prototype is written for the
> function, it will have to use the promoted type, that is to say:
> 
> 	unsigned char st_linear_to_Alaw (int sample);
> 
> Lastly, why is the type short being used at all? The advantage of short
> is that it may provide a compact representation for a large array of
> integers, provided that a range no wider than -32767 to 32767 is required
> (the minimum range required by ANSI/ISO C for the type short).
> 
[...]


So we can say in summary that Ada helps when people make mistakes?

Dale

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Joe Maun]

Kaz Kylheku wrote:
> 
> In article <3B83F042.4CFB073D@home.com>, Warren W. Gay VE3WWG wrote:
> >#define ACLIP 31744
> >...
> >unsigned char
> >st_linear_to_Alaw( sample )
> >short sample;
> >    {
> >    static const unsigned char exp_lut[128] = { ...snip... };
> >    int sign, exponent, mantissa;
> >    unsigned char Alawbyte;
> >
> >    /* Get the sample into sign-magnitude. */
> >    sign = ((~sample) >> 8) & 0x80;            /* set aside the sign */

[...]

> The way the sign is detected is completely braindamaged; it assumes
> that signed short is 16 bits wide, so that shifting it 8 bits
> to the right will cause the sign bit to land in position 7.

It's even more brain damaged than that. It assumes that /int/ is 16
bits.

> Also, shifting right a signed quantity whose sign bit is 1 is
> implementation-defined;

This doesn't matter in this case. The value that the vacated bits take
is indeed implementation defined, but the sign bit must reliably be
shifted into the required position, since nothing frees it from the
requirement that "The result of E1 >> E2 is E1 right-shifted E2 bit
positions".

> I think it's undefined in C99.

No, it isn't.

-- 
Joe Maun
Montreal, QC
Canada

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[David Starner]

On Wed, 22 Aug 2001 20:34:27 GMT, Kaz Kylheku <kaz@ashi.footprints.net> wrote:
> So we could say a number of things besides ``sox is written in the
> wrong programming language''.

Go ahead, blame the programmer. But don't forget that this is a real
program, in real use. The real world is not going to give you nice
friendly programs. Several months ago, Linux Weekly News pointed out
a email to linux-kernel showing stupid bugs in the Linux kernel; stuff 
like a = b++ + b++, and other undefined stuff. But, still, if that
blows up in the programmer's face, it's his fault, isn't it.
 
> If this function is submitted for critique to comp.lang.c, the errors
> in it will be shaken out in an instant, and a maximally portable version
> will soon appear that will work on C implementations with unusual sizes
> of integral types, CHAR_BIT other than 8, and sign-magnitude or ones'
> complement representations for negative numbers. Try it!

Cool. Should I upload the entire Linux kernel in one post, or should I
break it into two or three?

Yeah, a group of experts can pound a short piece of code into near
perfection in a short period of time, irrespective of language. The
question is how can Joe Random programmer turn out the largest amount
of code in the shortest time with the fewest bugs?

> If I ported the essence of the algorithm to Common Lisp (for instance),
> then it will just work. 

With the restriction of being able to output the music to speakers
in real-time on a 486 or Pentium?

-- 
David Starner - dstarner98@aasaa.ofe.org
Pointless website: http://dvdeug.dhis.org
"I don't care if Bill personally has my name and reads my email and 
laughs at me. In fact, I'd be rather honored." - Joseph_Greg

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[David Starner]

On Wed, 22 Aug 2001 18:55:46 GMT, Ted Dennison <dennison@telepath.com> wrote:
> Its truly *amazing* how many times I've heard that exact same story (although
> the other language is not always C). 

It's interesting that the C++ bug that got me to try Ada wouldn't have 
been fixed by Ada - I was trying to deallocate an item on the stack. But
I never would have made it in Ada; I never would have been messing with 
pointers in the first place, and I never would have mixed up getting a
pointer to an item with dereferencing an item in Ada.

-- 
David Starner - dstarner98@aasaa.ofe.org
Pointless website: http://dvdeug.dhis.org
"I don't care if Bill personally has my name and reads my email and 
laughs at me. In fact, I'd be rather honored." - Joseph_Greg

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Kaz Kylheku]

In article <9m1skf$8q81@news.cis.okstate.edu>, David Starner wrote:
>On Wed, 22 Aug 2001 20:34:27 GMT, Kaz Kylheku <kaz@ashi.footprints.net> wrote:
>> So we could say a number of things besides ``sox is written in the
>> wrong programming language''.
>
>Go ahead, blame the programmer. But don't forget that this is a real
>program, in real use.

I know what sox is, I use it.

The Ada and Lisp communities haven't decided to develop a replacement
for sox so far, so I'll just have to use the crummy C program for now
with its broken a-law conversion and all.

Where the culture is at now is that a large chunk of the useful programs
that others seem to be willing to share with me are written in C (or
some platform-specific dialects of it).

>> If I ported the essence of the algorithm to Common Lisp (for instance),
>> then it will just work. 
>
>With the restriction of being able to output the music to speakers
>in real-time on a 486 or Pentium?

There are Lisp compilers that produce machine code (e.g. CMUCL
http:/www.cons.org/cmucl). Performance-critical sections of code can be
tuned with various declarations to help speed things up.

It's hard to make concrete performance statements about abstract
languages!

If you make your selection of hardware slow and outdated enough, I
will eventually have to use assembly language to meet the performance
requirement, and at some point, I won't be able to meet it at all.

If the only way to meet a performance requirement is to use a stone age
programming language, or even assembly language, then by all means use it.

That doesn't justify the use of these languages for every single
programming task, or in fact for any part of a program except a few
performance hotspots.

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Jean-Pierre Rosen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 990 bytes --]


"Kaz Kylheku" <kaz@ashi.footprints.net> a �crit dans le message news: nHUg7.93012$B37.2083519@news1.rdc1.bc.home.com...
> So we could say a number of things besides ``sox is written in the
> wrong programming language''.
> [...]
>
> Would you hire the programmer who wrote this function, to work with you
> on a project in *any* programming language?
>
Yes, programmers make errors.

Two quotes that I love to bring together:
From one of the first books about C by K&R:
"C was designed on the assumption that the programmer is someone sensible who knows what he's doing"

From the introduction of the Ada Reference Manual:
"Ada was designed with the concern of programming as a human activity"

The fact that these starting hypothesis lead to two completely different philosophies of languages is left as a subject for
meditation...

--
---------------------------------------------------------
           J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Richard Bos]

"Jean-Pierre Rosen" <rosen@adalog.fr> wrote:

> From one of the first books about C by K&R:
> "C was designed on the assumption that the programmer is someone sensible who knows what he's doing"
> 
> From the introduction of the Ada Reference Manual:
> "Ada was designed with the concern of programming as a human activity"
> 
> The fact that these starting hypothesis lead to two completely different philosophies
> of languages is left as a subject for meditation...

<troll level="quite high>

The conclusion is obvious. C was designed for professionals; Ada for
amateurs.

</troll>

<nasty g>

Richard

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Gautier Write-only-address]

> > From one of the first books about C by K&R:
> > "C was designed on the assumption that the programmer is someone 
>sensible who knows what he's doing"
> >
> > From the introduction of the Ada Reference Manual:
> > "Ada was designed with the concern of programming as a human activity"

> > The fact that these starting hypothesis lead to two completely different 
>philosophies
> > of languages is left as a subject for meditation...

><troll level="quite high>
>
>The conclusion is obvious. C was designed for professionals; Ada for
>amateurs.
>
></troll>
>
><nasty g>

Essay of conclusion on conslusion: trolls are amateur, professionals
hope not to be human.

Next one ?


_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[James Rogers]

Richard Bos wrote:
> 
> "Jean-Pierre Rosen" <rosen@adalog.fr> wrote:
> 
> > From one of the first books about C by K&R:
> > "C was designed on the assumption that the programmer is someone sensible who knows what he's doing"
> >
> > From the introduction of the Ada Reference Manual:
> > "Ada was designed with the concern of programming as a human activity"
> >
> > The fact that these starting hypothesis lead to two completely different philosophies
> > of languages is left as a subject for meditation...
> 
> <troll level="quite high>
> 
> The conclusion is obvious. C was designed for professionals; Ada for
> amateurs.
> 
> </troll>

<troll level="current amplitude">

No, C was designed by naive optomists. Ada was designed by realists.

</troll>

Jim Rogers
Colorado Springs, Colorado USA

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Samuel T. Harris]

Richard Bos wrote:
> 
> "Jean-Pierre Rosen" <rosen@adalog.fr> wrote:
> 
> > From one of the first books about C by K&R:
> > "C was designed on the assumption that the programmer is someone sensible who knows what he's doing"
> >
> > From the introduction of the Ada Reference Manual:
> > "Ada was designed with the concern of programming as a human activity"
> >
> > The fact that these starting hypothesis lead to two completely different philosophies
> > of languages is left as a subject for meditation...
> 
> <troll level="quite high>
> 
> The conclusion is obvious. C was designed for professionals; Ada for
> amateurs.
> 
> </troll>
> 
> <nasty g>
> 
> Richard

Of course, _any_ professional engaged in a code base which
severly exceeds his span of attention and control can only be
expected to behave as well as an amateur.

-- 
Samuel T. Harris, Senior Software Engineer II
Raytheon, Aerospace Engineering Services
"If you can make it, We can fake it!"

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Marin David Condic]

Optimists are forever being disappointed. Pessimists are occasionally
pleasantly surprised.

I think the invention of C was a direct attempt to violate Murphy's Law. To
paraphrase Homer Simpson: "In the Ada community, we obey Murphy's Law!" :-)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"James Rogers" <jimmaureenrogers@worldnet.att.net> wrote in message
news:3B84F0DA.BE8B4D61@worldnet.att.net...
>
> <troll level="current amplitude">
>
> No, C was designed by naive optomists. Ada was designed by realists.
>
> </troll>

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Richard Bos]

Ted Dennison<dennison@telepath.com> wrote:

> In article <3b84cf73.1201990748@news.worldonline.nl>, Richard Bos says...
>
> >The conclusion is obvious. C was designed for professionals; Ada for
> >amateurs.
> 
> There are two problems with that statement:
> 
> 1) The only differece between "professionals" and "ameteurs" in our industry is
> that one of them is paid.
> 
> 2) A little digging into the history of both languages will actually show you
> that more or less the exact *opposite* of what you said was true. 

Good Cthulhu. The number of imbecilic Merkins who take irony seriously,
_even_ when marked as such, is truly stunning. I'm appalled.

Richard

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Ted Dennison]

In article <3b84cf73.1201990748@news.worldonline.nl>, Richard Bos says...
>
>> The fact that these starting hypothesis lead to two completely different 
>> philosophies of languages is left as a subject for meditation...
>The conclusion is obvious. C was designed for professionals; Ada for
>amateurs.

There are two problems with that statement:

1) The only differece between "professionals" and "ameteurs" in our industry is
that one of them is paid.

2) A little digging into the history of both languages will actually show you
that more or less the exact *opposite* of what you said was true. 

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
          home email - mailto:dennison@telepath.com

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[David Starner]

On Thu, 23 Aug 2001 09:42:58 GMT, Richard Bos <info@hoekstra-uitgeverij.nl> wrote:
><troll level="quite high>
> 
> The conclusion is obvious. C was designed for professionals; Ada for
> amateurs.
> 
></troll>

In which case, it has been satisfactorily proved that the Sox 
programmers are amateurs and should have been using Ada. 

-- 
David Starner - dstarner98@aasaa.ofe.org
Pointless website: http://dvdeug.dhis.org
"I don't care if Bill personally has my name and reads my email and 
laughs at me. In fact, I'd be rather honored." - Joseph_Greg

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Richard Riehle]

Richard Bos wrote:

> The conclusion is obvious. C was designed for professionals; Ada for
> amateurs.

I am no fan of the C family of languages.  However,  neither C or C++ are
inherently evil.   It is simply that they are more fraught with peril than
Ada or Modula-X.  Dr. Stroustrup did a brilliant job of making C a better,
safer language.    The inherent peril of C could not be totally eradicated
in the C++ model.   Subsequent efforts to improve C++ are commendable
and progress is evident.  Still, the underlying peril persists.    Mr. Gosling
and his colleagues made some good progress in eliminating some of the
perils of C and C++ with their design of Java.   Still, many of those
underlying perils persist.

The fact is that, even with the impressive progress that has been made in
the improvement of the C family of languages, they still do not measure
up to the inherent safety one finds in Ada.   It is very difficult to take a
language where the default is unsafe and promote it to one that is more
safe.   In Ada, the default is "safe" and that is what makes it appropriate
for software targeted to applications where lives are at stake.   I find
it odd that this is so difficult to understand.   Perhaps those in the community
that favors the C family of languages simply don't know Ada well enough
to comprehend the difference.   Perhaps they simply have other motives.

Whatever the case, no one is going to be persuaded by arguments presented
in this forum.   C++ will continue to be used successfully for a variety of
software applications, as will Ada.  Those of of us who prefer Ada will
still prefer it.  Those who prefer C++ will still choose it over Ada.  Those
who wish to rush off to the latest fad will choose Ruby, Erlang, C#, Java,
or whatever they, as early adopters, find interesting.

In my mind, choosing the right tool for the right job is important.   For anything
safety-related, Ada is still the right choice.   For anything else, I have no
serious objection to using C++.  It is a pretty well-designed attempt at
overcoming the perils of C.    Meanwhile,  there is someone, in some lab
somewhere inventing the safety-critical successor to Eiffel that will take
the industry by storm and make everything we currently favor obsolete.

Richard Riehle
richard@adaworks.com
http://www.adaworks.com

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[CBFalconer]

David Starner wrote:
> 
> On Thu, 23 Aug 2001 09:42:58 GMT, Richard Bos <info@hoekstra-uitgeverij.nl> wrote:
> ><troll level="quite high>
> >
> > The conclusion is obvious. C was designed for professionals;
> > Ada for amateurs.
> >
> ></troll>
> 
> In which case, it has been satisfactorily proved that the Sox
> programmers are amateurs and should have been using Ada.

Just because the Red Sox are 5 games behind the Yankees?

-- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@XXXXworldnet.att.net)
   (Remove "XXXX" from reply address. yahoo works unmodified)
   mailto:uce@ftc.gov  (for spambots to harvest)

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Dan Cross]

In article <3B855750.466C59CF@yahoo.com>,
CBFalconer  <cbfalconer@worldnet.att.net> wrote:
>> In which case, it has been satisfactorily proved that the Sox
>> programmers are amateurs and should have been using Ada.
>
>Just because the Red Sox are 5 games behind the Yankees?

Well, honestly, whaddya expect?  Of course they're behind the Yankees;
they're an inferior team.

	- Dan C.

(I guess I should note that I live a block away from the #4 train that
stops at Yankee Stadium in the Bronx; maybe I'm slightly biased.)

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[CBFalconer]

Dan Cross wrote:
> 
> In article <3B855750.466C59CF@yahoo.com>,
> CBFalconer  <cbfalconer@worldnet.att.net> wrote:
> >> In which case, it has been satisfactorily proved that the Sox
> >> programmers are amateurs and should have been using Ada.
> >
> >Just because the Red Sox are 5 games behind the Yankees?
> 
> Well, honestly, whaddya expect?  Of course they're behind the Yankees;
> they're an inferior team.
> 
>         - Dan C.
> 
> (I guess I should note that I live a block away from the #4 train that
> stops at Yankee Stadium in the Bronx; maybe I'm slightly biased.)

You are a braver man than I am.

-- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@XXXXworldnet.att.net)
   (Remove "XXXX" from reply address. yahoo works unmodified)
   mailto:uce@ftc.gov  (for spambots to harvest)

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Igor Tandetnik]

"Joe Maun" <reply_to@yahoo.com> wrote in message
news:3B8462C8.5596C089@yahoo.com...
> Kaz Kylheku wrote:
> > Also, shifting right a signed quantity whose sign bit is 1 is
> > implementation-defined;
>
> This doesn't matter in this case. The value that the vacated bits take
> is indeed implementation defined, but the sign bit must reliably be
> shifted into the required position, since nothing frees it from the
> requirement that "The result of E1 >> E2 is E1 right-shifted E2 bit
> positions".
>
> > I think it's undefined in C99.
>
> No, it isn't.
>
> --
> Joe Maun
> Montreal, QC
> Canada

I don't know. C99 says: "If E1 has a signed type and a negative value, the
resulting value is implementation-defined." It says the whole result of the
shift is implementation-defined, not that the bits to the left of original
bits are implementation-defined. I don't see any guarantee that original
bits have to be preserved.

C++ standard has the same exact wording.
--
With best wishes,
    Igor Tandetnik

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[pete]

Igor Tandetnik wrote:
> 
> "Joe Maun" <reply_to@yahoo.com> wrote in message
> news:3B8462C8.5596C089@yahoo.com...
> > Kaz Kylheku wrote:
> > > Also, shifting right a signed quantity whose sign bit is 1 is
> > > implementation-defined;
> >
> > This doesn't matter in this case. The value that the vacated bits take
> > is indeed implementation defined, but the sign bit must reliably be
> > shifted into the required position, since nothing frees it from the
> > requirement that "The result of E1 >> E2 is E1 right-shifted E2 bit
> > positions".
> >
> > > I think it's undefined in C99.
> >
> > No, it isn't.

> 
> I don't know. C99 says: 
> "If E1 has a signed type and a negative value, 
> the resulting value is implementation-defined."
> It says the whole result of the shift is implementation-defined, 
> not that the bits to the left of original bits are 
> implementation-defined. I don't see any guarantee that original
> bits have to be preserved.

> C++ standard has the same exact wording.

The propagation of the high order bit when a signed integer
is shifted right is THE example of implementation-defined behavior.

-- 
 pete

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Florian Weimer]

Joe Maun <reply_to@yahoo.com> writes:

> This doesn't matter in this case. The value that the vacated bits take
> is indeed implementation defined, but the sign bit must reliably be
> shifted into the required position, since nothing frees it from the
> requirement that "The result of E1 >> E2 is E1 right-shifted E2 bit
> positions".

What abound sign/magnitude representation of signed integers?

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Igor Tandetnik]

"pete" <pfiland@mindspring.com> wrote in message
news:3B888631.204F@mindspring.com...
> Igor Tandetnik wrote:
> >
> > "Joe Maun" <reply_to@yahoo.com> wrote in message
> > news:3B8462C8.5596C089@yahoo.com...
> > > Kaz Kylheku wrote:
> > > > Also, shifting right a signed quantity whose sign bit is 1 is
> > > > implementation-defined;
> > >
> > > This doesn't matter in this case. The value that the vacated bits take
> > > is indeed implementation defined, but the sign bit must reliably be
> > > shifted into the required position, since nothing frees it from the
> > > requirement that "The result of E1 >> E2 is E1 right-shifted E2 bit
> > > positions".
> > >
> > > > I think it's undefined in C99.
> > >
> > > No, it isn't.
>
> >
> > I don't know. C99 says:
> > "If E1 has a signed type and a negative value,
> > the resulting value is implementation-defined."
> > It says the whole result of the shift is implementation-defined,
> > not that the bits to the left of original bits are
> > implementation-defined. I don't see any guarantee that original
> > bits have to be preserved.
>
> > C++ standard has the same exact wording.
>
> The propagation of the high order bit when a signed integer
> is shifted right is THE example of implementation-defined behavior.

The question is not what happens to high-order bits that are introduced by
the shift - it is clear that the standards make no guarantee about it and
leave it to implementation. The question is what happens to the bits that
were there before the shift - do the standards guarantee that all of the
original bits (except low-order ones shifted away) are preserved albeit
shifted from their original positions?

Joe Maun says that one can reliably examine the sign bit even after it was
shifted from its original leftmost position. I argue that the standards
specify that all the bits of the result of the shift operation are
implementation-defined - not just high-order bits that the shift introduces.
--
With best wishes,
    Igor Tandetnik

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Joe Maun]

Igor Tandetnik wrote:
> 
> Joe Maun says that one can reliably examine the sign bit even after it was
> shifted from its original leftmost position. I argue that the standards
> specify that all the bits of the result of the shift operation are
> implementation-defined - not just high-order bits that the shift introduces.

The standards say that the *value* resulting from the expression is
implementation-defined. They also say that the result is "E1
right-shifted E2 bit positions". Since these two statements are not
contradictory (not specifying the high order bits is sufficient to make
the /value/ implementation defined), why do you think the latter doesn't
apply?

-- 
Joe Maun
Montreal, QC
Canada

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Joe Maun]

Florian Weimer wrote:
> 
> Joe Maun <reply_to@yahoo.com> writes:
> 
> > This doesn't matter in this case. The value that the vacated bits take
> > is indeed implementation defined, but the sign bit must reliably be
> > shifted into the required position, since nothing frees it from the
> > requirement that "The result of E1 >> E2 is E1 right-shifted E2 bit
> > positions".
> 
> What abound sign/magnitude representation of signed integers?

What about them?

-- 
Joe Maun
Montreal, QC
Canada

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Kaz Kylheku]

In article <tc8i7.54354$l7.6548595@typhoon.nyc.rr.com>, Igor Tandetnik wrote:
>
>The question is not what happens to high-order bits that are introduced by
>the shift - it is clear that the standards make no guarantee about it and
>leave it to implementation. The question is what happens to the bits that
>were there before the shift - do the standards guarantee that all of the
>original bits (except low-order ones shifted away) are preserved albeit
>shifted from their original positions?

``Implementation-defined'' refers to the entire resulting value. An
implementation could document and implement the behavior ``whenever a
signed integral value with a 1 in its sign bit is shifted right, the
resulting value is 42''.

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Igor Tandetnik]

"Joe Maun" <reply_to@yahoo.com> wrote in message
news:3B89A7D4.6E7A8BC4@yahoo.com...
> Igor Tandetnik wrote:
> >
> > Joe Maun says that one can reliably examine the sign bit even after it
was
> > shifted from its original leftmost position. I argue that the standards
> > specify that all the bits of the result of the shift operation are
> > implementation-defined - not just high-order bits that the shift
introduces.
>
> The standards say that the *value* resulting from the expression is
> implementation-defined. They also say that the result is "E1
> right-shifted E2 bit positions". Since these two statements are not
> contradictory (not specifying the high order bits is sufficient to make
> the /value/ implementation defined), why do you think the latter doesn't
> apply?

On one hand, I can see how the standard can be read your way. On the other
hand, I can't say that this clause in the standard is absolutely clear and
unambiguous. My opinion is that those two statements can be considered
contradictory, and, just to be on the safe side, I would not recommend
relying on the result of righ-shifting a negative value in a code intended
to be portable.
--
With best wishes,
    Igor Tandetnik

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Florian Weimer]

Joe Maun <reply_to@yahoo.com> writes:

>> > This doesn't matter in this case. The value that the vacated bits take
>> > is indeed implementation defined, but the sign bit must reliably be
>> > shifted into the required position, since nothing frees it from the
>> > requirement that "The result of E1 >> E2 is E1 right-shifted E2 bit
>> > positions".
>> 
>> What about sign/magnitude representation of signed integers?
>
> What about them?

The sign bit won't be shifted right, so you can't extract it using the
method given above.

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Joe Maun]

Florian Weimer wrote:
> 
> Joe Maun <reply_to@yahoo.com> writes:
> 
> >> > This doesn't matter in this case. The value that the vacated bits take
> >> > is indeed implementation defined, but the sign bit must reliably be
> >> > shifted into the required position, since nothing frees it from the
> >> > requirement that "The result of E1 >> E2 is E1 right-shifted E2 bit
> >> > positions".
> >>
> >> What about sign/magnitude representation of signed integers?
> >
> > What about them?
> 
> The sign bit won't be shifted right, so you can't extract it using the
> method given above.

I fail to see your point. Why wouldn't the sign bit be shifted right in
sign magnitude representation? The quote from the standard above seems
clear - and it applies to a signed magnitude implementation as well.

-- 
Joe Maun
Montreal, QC
Canada

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Florian Weimer]

Joe Maun <reply_to@yahoo.com> writes:

> I fail to see your point. Why wouldn't the sign bit be shifted right in
> sign magnitude representation? The quote from the standard above seems
> clear - and it applies to a signed magnitude implementation as well.

What about this quote from the standard, then?

| 3.4.1
| [#1] implementation-defined behavior
| unspecified behavior where each implementation documents how
| the choice is made
|
| [#2] EXAMPLE  An example of implementation-defined  behavior
| is  the  propagation  of  the  high-order  bit when a signed
| integer is shifted right.

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Joe Maun]

Florian Weimer wrote:
> 
> Joe Maun <reply_to@yahoo.com> writes:
> 
> > I fail to see your point. Why wouldn't the sign bit be shifted right in
> > sign magnitude representation? The quote from the standard above seems
> > clear - and it applies to a signed magnitude implementation as well.
> 
> What about this quote from the standard, then?
> 
> | 3.4.1
> | [#1] implementation-defined behavior
> | unspecified behavior where each implementation documents how
> | the choice is made
> |
> | [#2] EXAMPLE  An example of implementation-defined  behavior
> | is  the  propagation  of  the  high-order  bit when a signed
> | integer is shifted right.

I'm afraid you missed the point. As has already been pointed out, the
discussion isn't about the new high-order bits that the shift
introduces, which is what the quote above mentions. Everybody agrees
that that's implementation defined. The question is what about the bits
that already exist - are they guaranteed to be reliably shifted right? I
say yes, some say no.

If anything, the quote above strongly hints that the intention of the
standard is as I argue, since it only mentions the propagation of the
_high order bit_ as implementation defined.

-- 
Joe Maun
Montreal, QC
Canada

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Kaz Kylheku]

In article <3B8B1130.97FFDD66@yahoo.com>, Joe Maun wrote:
>Florian Weimer wrote:
>> 
>> Joe Maun <reply_to@yahoo.com> writes:
>> 
>> > I fail to see your point. Why wouldn't the sign bit be shifted right in
>> > sign magnitude representation? The quote from the standard above seems
>> > clear - and it applies to a signed magnitude implementation as well.
>> 
>> What about this quote from the standard, then?
>> 
>> | 3.4.1
>> | [#1] implementation-defined behavior
>> | unspecified behavior where each implementation documents how
>> | the choice is made
>> |
>> | [#2] EXAMPLE  An example of implementation-defined  behavior
>> | is  the  propagation  of  the  high-order  bit when a signed
>> | integer is shifted right.
>
>I'm afraid you missed the point. As has already been pointed out, the
>discussion isn't about the new high-order bits that the shift
>introduces, which is what the quote above mentions. Everybody agrees
>that that's implementation defined. The question is what about the bits
>that already exist - are they guaranteed to be reliably shifted right? I
>say yes, some say no.

I have a C99 draft copy which says:

``If E1 has a signed type, and a negative value, the resulting value
is implementation-defined.''

What is so hard to understand about this? 

There is absolutely no ambiguity about what it means for a resulting
value to be implementation-defined. This is not some gray area of
the language about which only experts can have doubts.

Implementation-defined could mean that the value 42 is always computed
regardless of the value of the remaining bits, or the shift amount.

If the intent was only to leave the treatment of the sign bit to
the implementors, then the text would say something else entirely,
like perhaps ``If E1 has a signed type and a negative value, it is
implementation-defined whether or not the sign bit is involved in the
shift operation. If it is involved, it's implementation-defined whether
or not it is replaced by a 1 or 0 bit''.

>If anything, the quote above strongly hints that the intention of the
>standard is as I argue, since it only mentions the propagation of the
>_high order bit_ as implementation defined.

Computing the value 42 is a perfect example of such propagation.
The sign bit propagates to bit positions 1, 3 and 4. Its complemented
value propagates to all other bits.

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Joe Maun]

Kaz Kylheku wrote:
> 
> In article <3B8B1130.97FFDD66@yahoo.com>, Joe Maun wrote:
[...]
> >introduces, which is what the quote above mentions. Everybody agrees
> >that that's implementation defined. The question is what about the bits
> >that already exist - are they guaranteed to be reliably shifted right? I
> >say yes, some say no.
> 
> I have a C99 draft copy which says:
> 
> ``If E1 has a signed type, and a negative value, the resulting value
> is implementation-defined.''
> 
> What is so hard to understand about this?
> 
> There is absolutely no ambiguity about what it means for a resulting
> value to be implementation-defined.

Right. However, while the value computed is implementation-defined, the
state of some bits is not necessarily so. Unlike most other operators,
the shift operators are defined both in terms of bits *and* values, two
different concepts.

When a particular aspect of the standard is implementation defined, the
behavior chosen by the implementation has no license to violate a
different aspect of the standard. So while the *whole* value is indeed
implementation defined (there is no such thing as a partial value), I
don't see where it gets the license to violate "The result of E1 >> E2
is E1 right-shifted E2 bit positions", which is not specified in terms
of values but in terms of bits.

So while the value of the expression is explicitly implementation
defined, the state of the bits that existed before the shift are well
defined by the first sentence of that clause, which is _not_
contradicted by the quote "the resulting value is
implementation-defined", since they are two different aspects of the
shift operators.

> This is not some gray area of
> the language about which only experts can have doubts.

Obviously, since I too have doubts. Since you mentioned "experts", it
may be interesting to point out that I changed my position on this after
I was corrected by Lawrence K. when I claimed as you do now. See:

http://groups.google.com/groups?as_umsgid=984786377snz%40genesis.demon.co.uk

For a definitive answer (or more likely endless debate) perhaps this
should be posted to comp.std.c(++).

-- 
Joe Maun
Montreal, QC
Canada

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Kaz Kylheku]

In article <3B8BD171.32C155D2@yahoo.com>, Joe Maun wrote:
>Kaz Kylheku wrote:
>> 
>> In article <3B8B1130.97FFDD66@yahoo.com>, Joe Maun wrote:
>[...]
>> >introduces, which is what the quote above mentions. Everybody agrees
>> >that that's implementation defined. The question is what about the bits
>> >that already exist - are they guaranteed to be reliably shifted right? I
>> >say yes, some say no.
>> 
>> I have a C99 draft copy which says:
>> 
>> ``If E1 has a signed type, and a negative value, the resulting value
>> is implementation-defined.''
>> 
>> What is so hard to understand about this?
>> 
>> There is absolutely no ambiguity about what it means for a resulting
>> value to be implementation-defined.
>
>Right. However, while the value computed is implementation-defined, the
>state of some bits is not necessarily so.

An implementation-defined result gives the implementor complete freedom
to choose the algorithm by which the result is selected.  It's the same
as unspecified behavior, except for the requirement to document.

If the standard wanted to narrow down the selection, then the wording
would contain the necessary refinements, with references to the behavior
of particular bits.

>Unlike most other operators,
>the shift operators are defined both in terms of bits *and* values, two
>different concepts.

I don't see any reference to bits in the sentence ``If E1 has a signed
type, and a negative value, the resulting value is implementation-defined''.

>When a particular aspect of the standard is implementation defined, the
>behavior chosen by the implementation has no license to violate a
>different aspect of the standard. So while the *whole* value is indeed
>implementation defined (there is no such thing as a partial value), I
>don't see where it gets the license to violate "The result of E1 >> E2
>is E1 right-shifted E2 bit positions", which is not specified in terms
>of values but in terms of bits.

The entire paragraph from C99 says this:

	The result of E1 >> E2 is right shifted E2 bit positions.
	If E1 has an unsigned type, or if E1 has a signed type and
	a nonnegative value, the value of the result is the integral
	part of the quotient of E1 divided by the quantity, 2 raised to
	the power of E2. If E1 has a signed type and a negative value,
	the resulting value is implementation-defined.

So you see, when the result is not implementation-defined, it is actually
defined *arithmetically* as the quotient of an integer division by a power
of two.

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Joe Maun]

Kaz Kylheku wrote:

> The entire paragraph from C99 says this:
> 
>         The result of E1 >> E2 is right shifted E2 bit positions.
>         If E1 has an unsigned type, or if E1 has a signed type and
>         a nonnegative value, the value of the result is the integral
>         part of the quotient of E1 divided by the quantity, 2 raised to
>         the power of E2. If E1 has a signed type and a negative value,
>         the resulting value is implementation-defined.
> 
> So you see, when the result is not implementation-defined, it is actually
> defined *arithmetically* as the quotient of an integer division by a power
> of two.

The *value* is defined arithmetically, while the bit positions are
defined in terms of bit-shifts. Both are properties of the shift
operator. When one is implementation defined, the other may still be
well defined. What do you think the first sentence is there for?

-- 
Joe Maun
Montreal, QC
Canada

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Kaz Kylheku]

In article <3B8BED46.3DEE945B@yahoo.com>, Joe Maun wrote:
>Kaz Kylheku wrote:
>
>> The entire paragraph from C99 says this:
>> 
>>         The result of E1 >> E2 is right shifted E2 bit positions.
>>         If E1 has an unsigned type, or if E1 has a signed type and
>>         a nonnegative value, the value of the result is the integral
>>         part of the quotient of E1 divided by the quantity, 2 raised to
>>         the power of E2. If E1 has a signed type and a negative value,
>>         the resulting value is implementation-defined.
>> 
>> So you see, when the result is not implementation-defined, it is actually
>> defined *arithmetically* as the quotient of an integer division by a power
>> of two.
>
>The *value* is defined arithmetically, while the bit positions are
>defined in terms of bit-shifts. Both are properties of the shift

Under ones' complement, the bit pattern 1111...111 is non-negative;
it represents the value zero. When this is right shifted by 1, it must
result in the value 0. That value could be represented as 0000...00
or 1111...11.

>operator. When one is implementation defined, the other may still be
>well defined. What do you think the first sentence is there for?

I think it's superflous text that helps to clarify what the operator
is generally for. The subsequent sentences form an exhaustive partition
of all the possibilities: unsigned E1, non-negative signed E1,
and negative signed E1. Each partition of the E1 input is assigned
a behavior. The first two partitions have an arithmetically defined
resulting value. That value is positive, and therefore it has a
corresponding portable binary representation. So, effectively, in these
first two partitions, bit shifting behavior is specified implicitly
as a division by a power of two, without any useful contribution
from the first sentence.  The third partition leads to an
implementation-defined value, which could be anything.

If these sentences did not provide semantics for all the partitions,
then the first sentence would apply to the remaining cases that
are not covered.

So for instance, if nothing were mentioned about the handling of an
unsigned E1, then the interpretation would be that E1 is right shifted
E2 bit positions.

I believe that you have to apply the text which has the most specific
semantics for a given case; it overrides any general text.

The general text is that E1 >> E2 is E1 right shifted by E2 bits.
This is obviously not the case if the sign bit does not shift
along with the others.  If the value of the sign bit does shift along
with the others, then the only question that remains is what 
replaces its value: is a 1 shifted in or a 0? Under two's complement,
these two possibilities are called arithmetic and logical shift.  If the
only question were what value is shifted in, then the standard could
easily have specific text to that effect.  As it stands, the general
text is at odds with the specific text for negative E1. The specific
text dominates.

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Kaz Kylheku]

In article <3B8BED46.3DEE945B@yahoo.com>, Joe Maun wrote:
>Kaz Kylheku wrote:
>
>> The entire paragraph from C99 says this:
>> 
>>         The result of E1 >> E2 is right shifted E2 bit positions.
>>         If E1 has an unsigned type, or if E1 has a signed type and
>>         a nonnegative value, the value of the result is the integral
>>         part of the quotient of E1 divided by the quantity, 2 raised to
>>         the power of E2. If E1 has a signed type and a negative value,
>>         the resulting value is implementation-defined.
>> 
>> So you see, when the result is not implementation-defined, it is actually
>> defined *arithmetically* as the quotient of an integer division by a power
>> of two.
>
>The *value* is defined arithmetically, while the bit positions are
>defined in terms of bit-shifts. Both are properties of the shift

Under ones' complement, the bit pattern 1111...111 is non-negative;
it represents the value zero. When this is right shifted by 1, it must
result in the value 0. That value could be represented as 0000...00
or 1111...11.

What about the sign-magnitude zero, 1000...000? When that is shifted
right, you can get 1000..000 or 0000..000. Is that a bit shift?

>operator. When one is implementation defined, the other may still be
>well defined. What do you think the first sentence is there for?

I think it's superflous text that helps to clarify what the operator
is generally for. The subsequent sentences form an exhaustive partition
of all the possibilities: unsigned E1, non-negative signed E1,
and negative signed E1. Each partition of the E1 input is assigned
a behavior. The first two partitions have an arithmetically defined
resulting value. That value is positive, and therefore it has a
corresponding portable binary representation. So, effectively, in these
first two partitions, bit shifting behavior is specified implicitly
as a division by a power of two, except in cases like the alternate zeros
in ones' complement and sign-magnitude.  The third partition leads to
an implementation-defined value, which could be anything.

If these sentences did not provide semantics for all the partitions,
then the first sentence would apply to the remaining cases that
are not covered.

So for instance, if nothing were mentioned about the handling of an
unsigned E1, then the interpretation would be that E1 is right shifted
E2 bit positions.

I believe that you have to apply the text which has the most specific
semantics for a given case; it overrides any general text.

The general text is that E1 >> E2 is E1 right shifted by E2 bits.
This is obviously not the case if the sign bit does not shift
along with the others.  If the value of the sign bit does shift along
with the others, then the only question that remains is what 
replaces its value: is a 1 shifted in or a 0? Under two's complement,
these two possibilities are called arithmetic and logical shift.  If the
only question were what value is shifted in, then the standard could
easily have specific text to that effect.  As it stands, the general
text is at odds with the specific text for negative E1. The specific
text dominates.

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Joe Maun]

Kaz Kylheku wrote:
> 
> In article <3B8BED46.3DEE945B@yahoo.com>, Joe Maun wrote:
> >Kaz Kylheku wrote:
> >
> >> The entire paragraph from C99 says this:
> >>
> >>         The result of E1 >> E2 is right shifted E2 bit positions.
> >>         If E1 has an unsigned type, or if E1 has a signed type and
> >>         a nonnegative value, the value of the result is the integral
> >>         part of the quotient of E1 divided by the quantity, 2 raised to
> >>         the power of E2. If E1 has a signed type and a negative value,
> >>         the resulting value is implementation-defined.
> >>
> >> So you see, when the result is not implementation-defined, it is actually
> >> defined *arithmetically* as the quotient of an integer division by a power
> >> of two.
> >
> >The *value* is defined arithmetically, while the bit positions are
> >defined in terms of bit-shifts. Both are properties of the shift
> 
> Under ones' complement, the bit pattern 1111...111 is non-negative;

Wrong. If it's not a trap representation it's *negative* zero (ISO/IEC
9899:1999 - 6.2.6.2[2]).

> it represents the value zero. When this is right shifted by 1, it must
> result in the value 0.

Since it is a negative value, the resulting value is
implementation-defined. The resulting bits must have the form ?111...11.

> That value could be represented as 0000...00
> or 1111...11.
> 
> What about the sign-magnitude zero, 1000...000?

That too is negative zero, so the above applies.

> When that is shifted
> right, you can get 1000..000 or 0000..000. Is that a bit shift?

You get ?100...00.

> easily have specific text to that effect.  As it stands, the general
> text is at odds with the specific text for negative E1. The specific
> text dominates.

Is it really at odds with the specific text? Or can both be satisfied? I
think both can be satisfied for reasons I have already mentioned. You
think they are meant to be at odds. I don't think I have anything to add
to this, so I probably won't, unless you come up with something really
convincing.

-- 
Joe Maun
Montreal, QC
Canada

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Larry Kilgallen]

In article <87d75fhaod.fsf@deneb.enyo.de>, Florian Weimer <fw@deneb.enyo.de> writes:
> Joe Maun <reply_to@yahoo.com> writes:
> 
>>> Under ones' complement, the bit pattern 1111...111 is non-negative;
>>
>> Wrong. If it's not a trap representation it's *negative* zero (ISO/IEC
>> 9899:1999 - 6.2.6.2[2]).
>>
>>> it represents the value zero. When this is right shifted by 1, it must
>>> result in the value 0.
>>
>> Since it is a negative value, the resulting value is
>> implementation-defined. The resulting bits must have the form ?111...11.
> 
> How do you derive that from the standard?  From the phrase 'The result
> of E1 >> E2 is E1 right-shifted E2 bit positions.'?  What happens when
> we write down the bits starting with the least significant bit?

That might depend on whether your "start" of writing is on
the left (European style) or the right (Arabic style) :-)

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Florian Weimer]

Joe Maun <reply_to@yahoo.com> writes:

> The *value* is defined arithmetically, while the bit positions are
> defined in terms of bit-shifts.

But where?  I haven't seen any definition of the term 'bit-shift'.  It
seems that you consider the introductory explanation of the relevant
parapgraph a definition, but most people do not seem to agree.

Sometimes I wish there was another version of the C standard which
contained the strictly normative parts. ;-)

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Florian Weimer]

Joe Maun <reply_to@yahoo.com> writes:

>> Under ones' complement, the bit pattern 1111...111 is non-negative;
>
> Wrong. If it's not a trap representation it's *negative* zero (ISO/IEC
> 9899:1999 - 6.2.6.2[2]).
>
>> it represents the value zero. When this is right shifted by 1, it must
>> result in the value 0.
>
> Since it is a negative value, the resulting value is
> implementation-defined. The resulting bits must have the form ?111...11.

How do you derive that from the standard?  From the phrase 'The result
of E1 >> E2 is E1 right-shifted E2 bit positions.'?  What happens when
we write down the bits starting with the least significant bit?

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[B.Gaffney]

Joe Maun <reply_to@yahoo.com> wrote in message news:<3B8BED46.3DEE945B@yahoo.com>...
> Kaz Kylheku wrote:
> 
> > The entire paragraph from C99 says this:
> > 
> >         The result of E1 >> E2 is right shifted E2 bit positions.
> >         If E1 has an unsigned type, or if E1 has a signed type and
> >         a nonnegative value, the value of the result is the integral
> >         part of the quotient of E1 divided by the quantity, 2 raised to
> >         the power of E2. If E1 has a signed type and a negative value,
> >         the resulting value is implementation-defined.
> > 
> > So you see, when the result is not implementation-defined, it is actually
> > defined *arithmetically* as the quotient of an integer division by a power
> > of two.
> 
> The *value* is defined arithmetically, while the bit positions are
> defined in terms of bit-shifts. Both are properties of the shift
> operator. When one is implementation defined, the other may still be
> well defined. What do you think the first sentence is there for?

But on a sign-magnitude machine it may make sense to exclude the sign
bit from this shift.  Is there anything in the standard which
specifies the bit layout or what a "right shift" is?  Does it specify
that it must include the sign bit?

From a practical perspective, if a compiler were implemented on such a
machine, it could take advantage of this "implementation-defined"
permission to allow it to optimize A/2 as A>>1 (i.e. if A = 42, A/2 =
A>>1 = 21 and if B = -42, B/2 = B>>1 = -21), which it couldn't do for
a signed type otherwise (assuming a 16-bit sign-magnitude type, B>>1 =
32747 <> B/2).

There are two "expectation" people have of a right shift (whatever the
standard actually says):  it is equivalent to a division by a power of
two and the sign bit is shifted.  On a sign-magnitude machine one of
the two will always fail, and some code with it.  It's up the the
implementation which way is 'best'.  (Good reason to stick with 2's
complement.)

BTW, what if a machine were implemented with the LSB on the left and
the MSB on the right?  Would A>>1 actually require a _left_ shift (per
the A/2 requirement above)?

          --Brian

Re: Subtle Bugs, kudos Ada (was How Ada ...Red Code ...)

[Darren New]

> BTW, what if a machine were implemented with the LSB on the left and
> the MSB on the right?  Would A>>1 actually require a _left_ shift (per
> the A/2 requirement above)?

Err, "left" and "right" don't make any sense when talking about machine
implementations. There's no reason to assume that different bits of the
same byte are in the same bank of memory chips, let alone where they are
on the die. :-)

Arabic numbers are written LSB on the right (which is the *first*
position in Arabic). This actually makes a lot more sense than having
the MSB come first.

Followups to comp.lang.c where they belong, thanks. :-)

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.