Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #67773 > unrolled thread

Re: the language (and the role of Undefined Behavior therein)

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-18 16:19 -0700
    Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-18 21:15 -0400
      Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-19 10:11 -0700
        Re: the language (and the role of Undefined Behavior therein) Ike Naar <ike@iceland.freeshell.org> - 2015-08-19 19:58 +0000
          Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-19 14:09 -0700
        Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-19 16:10 -0400
          Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-19 16:01 -0700
            Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-19 20:23 -0400
              Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 10:35 -0700
                Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-20 12:32 -0700
                  Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 13:31 -0700
                    Re: the language (and the role of Undefined Behavior therein) donalhambra@gmail.com - 2015-08-20 14:23 -0700
                      Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 16:13 -0700
                    Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-20 17:48 -0700
                      Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-21 01:32 -0700
                        Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-21 18:34 -0700
                          Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-21 22:11 -0700
                            Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-22 09:41 -0400
                              Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-22 16:59 +0000
                                Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-22 23:30 -0400
                                  Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-24 03:36 +0000
                                    Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-24 00:25 -0400
                                      Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 22:57 -0700
                                        Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-24 19:49 +0000
                                  Re: the language (and the role of Undefined Behavior therein) Tim Rentsch <txr@alumni.caltech.edu> - 2015-09-06 14:43 -0700
                              Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 16:27 -0700
                                Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-23 21:15 -0400
                                  Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 20:18 -0700
                            Re: the language (and the role of Undefined Behavior therein) raltbos@xs4all.nl (Richard Bos) - 2015-08-22 14:37 +0000
                          Re: the language (and the role of Undefined Behavior therein) David Kleinecke <dkleinecke@gmail.com> - 2015-08-22 19:12 -0700
                            Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-22 23:38 -0400
                              Re: the language (and the role of Undefined Behavior therein) David Kleinecke <dkleinecke@gmail.com> - 2015-08-23 20:01 -0700
                                Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-23 21:56 -0700
                                  Re: the language (and the role of Undefined Behavior therein) David Kleinecke <dkleinecke@gmail.com> - 2015-08-24 17:25 -0700
                                    Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-24 18:21 -0700
                                    Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-24 22:22 -0400
                                      Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-25 14:31 +0000
                                        Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-25 09:22 -0700
                                          Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-25 18:55 +0000
                                          Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-25 12:33 -0700
                                            Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-25 16:23 -0700
                                Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-24 00:31 -0400
                                  Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-24 10:32 -0700
                            Re: the language (and the role of Undefined Behavior therein) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-22 23:54 -0700
                            Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-24 03:45 +0000
                          Re: the language (and the role of Undefined Behavior therein) Tim Rentsch <txr@alumni.caltech.edu> - 2015-09-07 08:11 -0700
        Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-23 18:46 -0400
          Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 19:04 -0700
            Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-23 23:40 -0400
              Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 22:48 -0700
                Re: the language (and the role of Undefined Behavior therein) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-24 00:38 -0700
    Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-18 21:22 -0400
    Re: the language (and the role of Undefined Behavior therein) Ike Naar <ike@iceland.freeshell.org> - 2015-08-20 21:44 +0000
      Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 16:48 -0700
      Re: the language (and the role of Undefined Behavior therein) Philip Lantz <prl@canterey.us> - 2015-08-20 23:41 -0700

Page 3 of 3 — ← Prev page 1 2 [3]

#68350

On Tuesday, August 25, 2015 at 2:23:59 PM UTC-5, Keith Thompson wrote:
> Note that making -INT_MAX-1 a trap representation doesn't mean that any
> operation that yields that value has to "trap".  It merely means that
> such an operation has undefined behavior.

True.  Doing so may allow implementations to save a tiny bit on library code which would no longer have to handle a negative number that can't be made positive.  The PC version of Beyond Zork used to crash if the player sold the butterfly enough times, with its price doubling after each time, to yield a price of -32768 Zorkmids.  A price of -16834 or -24576 Zorkmids was harmless, but -32768 died.  The executable seems to have been produced using Microsoft C; I wonder if any MS printf-related or similar functions were quirky, or if it was a bug in the application's numeric-formatting code that caused the crash.

[toc] | [prev] | [next] | [standalone]

#68193

On 08/23/2015 11:01 PM, David Kleinecke wrote:
> On Saturday, August 22, 2015 at 8:38:24 PM UTC-7, James Kuyper wrote:
...
>> Unsigned int follows the rules of arithmetic modulo UINT_MAX+1; that
>> might be what you're thinking about.
>> -- 
>> James Kuyper
> 
> Signed arithmetic is also a version of modulo UINT_MAX+1 with a
> different way of writing some of the integers.

On most systems nowadays, that's true, but there are still exceptions,
and at the time that you're precious C90 was written, there were a lot
more, which is why C90 allows for other ways of representing signed
integers. I gather that C99 made this clearer, so I'm not sure what the
C90 wording was like, but it did allow for or 1's complement and
sign-magnitude representations, representations that were in actual use,
and still are, though to a much lesser extent.
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#68239

James Kuyper <jameskuyper@verizon.net> writes:
[...]
> On most systems nowadays, that's true, but there are still exceptions,
> and at the time that you're precious C90 was written, there were a lot
> more, which is why C90 allows for other ways of representing signed
> integers. I gather that C99 made this clearer, so I'm not sure what the
> C90 wording was like, but it did allow for or 1's complement and
> sign-magnitude representations, representations that were in actual use,
> and still are, though to a much lesser extent.

C90 required a "pure binary" representation for integer types,
but did go into details.  C90 did not mention one's complement or
sign-magnitude, and mentioned two's complement only in an example.

C99 introduced the restriction to one of three representation schemes
for signed integers.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#68096

On Sunday, August 23, 2015 at 3:13:06 AM UTC+1, David Kleinecke wrote:
>
> It is true that every computer I know about executes a multiplication
> into a "register" twice as long as the multipliers. But C simply 
> truncates that back modula INT_MAX+1 (actually it's bit more
> complicated. Even though C provides no way getting the higher half
> of a multiplication I enevr heard a complaint. Odd.
>
It's a nuisance if you're implementing bug nums.

Overflow is a constant niggle. But integers are almost always used
to index into arrays, even character types when you think about
it, or in intermediate calculations producing such indices. So
as long as an integer can index any array, it's big enough - you
can't handle any other values.
(Scaled integers aren't integers, they're a way of representing real
data. Sometimes, as with colour channels, you get so used to thinking
of them as being in the range 0-255 that you think of them as integers,
but of course they're not, alpha of 128 means "half", not a hundred
and twenty eight).

[toc] | [prev] | [next] | [standalone]

#68189

David Kleinecke <dkleinecke@gmail.com> wrote:

(snip)

> It is true that every computer I know about executes a multiplication
> into a "register" twice as long as the multipliers. But C simply 
> truncates that back modula INT_MAX+1 (actually it's bit more
> complicated. Even though C provides no way getting the higher half
> of a multiplication I enevr heard a complaint. Odd.   

I have complained, though not recently. In TeX, Knuth suggests that
one routine be rewritten in assembler if possible. That routine
does a multiply generating a double length product, and then uses
that as a dividend in a divide operation.

The processors (most) that generate a double length product also
usually accept a double length dividend. 

Though many processors generate the double length product,
they don't all do it the same way. Specifically, the way the
high bit of the low half is defined might be different.
That is especially true on sign magnitude and ones complement,
but I have seen it on twos complement, too.

-- glen

[toc] | [prev] | [next] | [standalone]

#69797

Keith Thompson <kst-u@mib.org> writes:

> supercat@casperkitty.com writes:
>> On Thursday, August 20, 2015 at 6:48:24 PM UTC-5, Keith Thompson wrote:
>>> I'm skeptical that such a change was made, but I'm more than willing to
>>> be convinced.  Can you cite the added wording in C11 that says this?
>>
>> Hmm... upon doing some further research, it seems I may have been
>> mistaken.
>>
>>>> By the mid 1980s, mainstream compilers for mainstream platforms had
>>>> pretty well established some de facto boundaries for the behaviors of
>>>> some actions where the standard imposed no requirements.  Thus, by the
>>>> mid 1990s, programmers faced with the choice of writing nasty code to
>>>> avoid overflow, or less-nasty code to limit the effects, would
>>>> generally perceive no reason to favor the former unless their code
>>>> would need to run on some really obscure hardware.
>>>
>>> In the mind 1980s, there was no C standard.
>>
>> I would say that the 1978 publication of The C Programming Language, by
>> Brian W. Kernighan and Dennis M.  Ritchie, established a C Standard.  I
>> don't know exactly when the new parameter specification form entered
>> mainstream use, but it was certainly before the 1989 publication of the
>> ANSI C Standard.  I first started programming with Turbo C in early
>> 1988, and nearly all the code I ever saw used the new form.
>
> Prototypes were invented in C++ and later added to C.  They were first
> *officially* introduced by the 1989 ANSI standard, but they were
> undoubtedly implemented and used before that (just because they were *so
> much better* than old-style function declarations).  There was also a
> tool called "ansi2knr" that would translate C code with prototypes to C
> code without prototypes, so you could use prototypes even if your
> compiler didn't yet support them.
>
>>> That sounds similar to SFINAE
>>>     https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error
>>> but that applies only when a template expansion would cause a
>>> compile-time error;  undefined behavior is not relevant.
>>
>> If evaluation of a compile-time constant in the course of a template
>> expansion would invoke Undefined Behavior (e.g. -1<<3), the Standard
>> mandates that the expansion be regarded as ill-formed, even if the
>> compiler's documentation would specify a behavior consistent with
>> yielding a constant (e.g. -8).
>
> [...]
>
>>> Certainly optimizers have simply gotten more clever over the years.
>>> I'm not aware of any sudden change of the kind you describe.
>>
>> Historically, most optimizers would perform transformations which would
>> be valid under some sort of execution model.
>
> [SNIP]
>
>> The hyper-modern philosophy is different, in that it makes it impossible
>> to define or constrain the effects of any sort of UB.  I don't have a
>> firm grasp as to when and how the philosophy took hold, but it seems to
>> have been sometime around 2009.
>
> The "hyper-modern philosophy" is the one that's been implicit in the C
> standard since 1989.  I haven't kept track of developments in
> optimization well enough to know how things have changed or when they've
> changed.  But if your program has potential undefined behavior, I suggest
> that you need to fix the program.  If you think that int n = INT_MAX;  n
> ++;  "should" set n to any particular value, that's not a conclusion that
> you can draw from the C standard.
>
> I do agree that compilers should do a better job of diagnosing such
> programs, especially when they take advantage of the presence of undefine
> behavior to perform "surprising" transformations.  I don't see the point
> of catering to such code beyond that.

Reading through the posting in this thread has been disappointing
for me, because I think supercat is raising some important issues
but mostly people aren't seeing that because his concerns are
expressed in a funny way.

For example, regarding "hyper-modern philosophy".  It's true that
the C standard has always allowed aggressive optimization that
takes advantage of undefined behavior, but AFAIK it is only
relatively recently that compilers have started to exploit that,
with results that are decidely counter-intuitive.  Moreover the
trend in this direction is getting worse - there was a case
recently where C semantics was "bent" (or interpreted in an
unusual way, if you will) to facilitate one of these unexpected
"optimizations".  I understand the desire of compiler writers to
optimize aggressively, but I think this tendency is getting out
of control to the point where the current rules no longer serve
the interests of developers.  The Linux kernel, to give a
prominent example, now requires semantic guarantees that C does
not provide, precisely to avoid these "optimizations".  There is
something wrong there.

A related point is that we would like to be able to write code in
certain cases that, even though it may produce a nonsensical
result under some circumstances, is not allowed arbitrary
transgressions as would be allowed under undefined behavior.
Unfortunately there is no middle ground - a result can be
undefined behavior, or unspecified behavior (which for current
purposes also includes implementation-defined behavior), but
nothing in between.  I don't know how common it is for such
situations to arise, but certainly they /can/ arise, and when
they do the current Standard offers no help.  IMO this matter
also bears further investigation.

Note that there is some precedent for these kinds of concerns in
official discussion.  C11 now has the notion of runtime
constraint violations, which is one method for addressing cases
that before would have been undefined behavior.  Also there have
been proposals for some form of limited undefined behavior, where
the consequences are not spelled out but not allowed to be as
disastrous as full undefined behavior.  Both of these are related
to the concerns that have been brought up in this thread.

I don't expect any great philosphical shifts in response to my
comments here, but I would like to ask those who have been
following the thread to read through the postings again keeping
the above remarks in mind.  I think some may find there is more
substance of interest than it appeared on first reading.

[toc] | [prev] | [next] | [standalone]

#68159

On 8/19/15 1:11 PM, supercat@casperkitty.com wrote:
> On Tuesday, August 18, 2015 at 8:15:50 PM UTC-5, Richard Damon wrote:
>>>       /* Requirement 2: If n is greater than 31, arbitrarily return either 0 or
>>>                         dat << (n & 31) */
>>>
>>
>> If you are going to write your requirements to match 'common' machines
>> in an attempt to optimize, you should be willing to expect that you are
>> going to rely on machine dependent behavior. This is NOT the case that
>> it will work naively on all machines. I seem to remember machines that
>> would trap on excessive value on over sized values on register based
>> shifts (I do admit it is very uncommon). If you want to be strictly
>> conforming, you need to be strictly conforming.
>
> My point is that since there are a substantial number of real-world
> applications where code returning either of the indicated values would
> be fine, and real-world processors are split as to which value they will
> naturally return, the goal of producing optimal machine code will be
> best realized if there is a way to indicate that either result will be
> acceptable; my preferred way of doing that would be to have a set of
> standardized macros that a program could use compile-time assertions
> with its requirements, such that every compiler would be required to
> either yield the behavior indicated by the macros or regard the program
> as ill-formed, and define a standard of compliance for programs which
> will yield correct behavior on any platform meeting the documented
> requirements.

Thinking about it, WHAT "real-world" application is going to over shift 
a value and work perfectly fine with either answer? (something beyond 
resorting to a GIGO argument on user input).

Also, I will point out that I can't imagine any compiler creating code 
for the shift function that is other than naive expectation of the 
machine shift code. Where the issue is that code CALLING the shift 
function, if the compiler is able to look inside and see the undefined 
behavior, may make (possible surprising) optimizations on the based on 
the assumed limited range of the shift count based on otherwise 
undefined behavior.
>
>> My guess is that even today, as an independent function most compilers
>> will do the simple thing in the original shift function. That IS the
>> simplest code. You may need to separately compile the function on an
>> aggressive compiler to keep it from propagating the permissions of
>> undefined behavior against the callers.
>
> Of course compilers would do the simple thing in a standalone
> function. The problem is that the only Standard-defined way to force
> them not to propagate UB against the caller is to explicitly specify a
> behavior which may be the simplest on some platforms, but needlessly
> complex on others.

the  a << (b & 0x1F) option should be simple on any reasonable platform, 
adding only an instruction or two to the sequence. Note also that this 
is only needed in the case of a program that overshifts and can accept 
this results (the likely result on most systems for at least slight 
overshifts if you ignored the UB).
>
>> Any decent compiler will use the int*int->long multiply instruction in
>> this case. It KNOWS the values are only int sized. Only a very dumb
>> compiler would slow down on this, and that one would likely do the
>> 'right' thing on the first case.
>
> Even if a compiler for a 16-bit machine recognizes that a 16x16->32
> multiply will suffice, casting to long would still require it to do work
> with the high-order word of the result which would be necessary to meet
> the C Standard, but useless from the perspective of meeting requirements.

Since was are assuming a 16x16->32 multiply (and a 16 bit int) the 
'extra' work is doing a 32 bit compare instead of 16 bit, which again is 
pretty small. Again you are using the

>
> Conversely, some 16-bit DSPs have a 16x16+32->32 multiply-accumulate
> instruction which would work very nicely to compute (long)a*b-(long)c*d,
> but could only compute the expression which truncated to unsigned and
> then to int by storing the first product to memory, computing the
> second, sign-extending that, and then subtracting the first.
>
>> Also, Undefined Behavior grants the implementation permission to break
>> the laws of time and causality, it doesn't grant it the ability. If the
>> implementers actually could break this, they are in the wrong business!
>
> Not really.
>
>      #include <stdio.h>
>
>      int blah(int mode, int a, int b)
>      {
>        printf("[%d %d]\n",a,b); flush(stdout);
>        if (mode == 33)
>          launch_nuclear_missiles(); // Terminates program execution
>        return mulcomp(a, 2, b, 3);
>      }
>
>      int main(void)
>      {
>        int ch = getch();
>        int sum;
>        sum += blah(9,ch,ch+2);
>        sum += blah(ch,INT_MAX,ch);
>        printf("%d",sum);
>        return 0;
>      }
>
> Program execution will be defined if ch equals 33. It might be
> defined
> on some platforms if ch is not 33 but a printf or flush(stdout) raises a
> SIGPIPE before the "if" gets invoked the second time. It the "if" gets
> reached the second time with any mode value other than 33, however, the
> Standard will allow the compiler is allowed to travel backward in time
> from the overflow in mulcomp() and decide that mode holds the value 33
> even if nothing ever assigns it that value.

The undefined behavior is allowed to call launch_nuclear_missiles(), and 
the as-if rule allows the order of execution to be largely re-arranged, 
so we have no temporal anomaly. (Since we have no volatile objects in 
the program, the only things that are "observable" are the getch(), the 
printf()s and the return from main, which need to happen in the 
specified order. Nothing using the value of ch is allowed to be moved 
before the getch() call, but other than that, the sequencing is not 
specified, as long as the rearrangement doesn't change defined behavior.

>
> BTW, suppose one wanted to make the indicated requirement for
> mulcomp() even on a platform where all signed types larger than char had
> the same positive range (legal if unsigned types have one more padding
> bit than signed types), would there be any strictly-compliant way one
> could write it that would be efficient and make its purpose obvious?
>

Yes, bypassing undefined behavior can be hard. Generally, making the 
routine a separately compiled function is enough to keep the UB from 
propagating out, as what the compiler can see, it can't use against you. 
There also is normally an implementation specific way to limit the 
optimizations to avoid this issue.

It is obvious that we will need to use some knowledge of the 
implementation to meet your requirement, as there are (or at least were) 
systems where this sort of undefined behavior did drastic things (like 
abending your program).

Of course, to meet your requirement f not violating causality, you need 
to add stuff to the code to force your idea of causality.

[toc] | [prev] | [next] | [standalone]

#68176

On Sunday, August 23, 2015 at 5:46:53 PM UTC-5, Richard Damon wrote:
> Thinking about it, WHAT "real-world" application is going to over shift 
> a value and work perfectly fine with either answer? (something beyond 
> resorting to a GIGO argument on user input).

(1) Applications frequently need to guarantee that malicious input will have
    no effect beyond yielding loosely-constrained garbage output.

(2) The normal way to write a "rotate left" function for rotate values 0-31
    used to be "(dat << n) | (dat >> (32-n))".  That expression will work the
    same regardless of whether "dat >> 32" yields dat or zero, and it's likely
    that if a compiler can optimize anything to a "rotate left" instruction it
    will optimize that.  Is anything gained by requiring programmers to use a
    longer and ickier form?

(3) Many functions sometimes pay attention to certain arguments and sometimes
    ignore them.  If the cases which would result in a value being shifted
    by an excessive amount are also cases where its value will be ignored,
    but no other special handling would be needed at the point of the shift,
    letting the shift happen may be more efficient than adding code to prevent
    it.

> Also, I will point out that I can't imagine any compiler creating code 
> for the shift function that is other than naive expectation of the 
> machine shift code. Where the issue is that code CALLING the shift 
> function, if the compiler is able to look inside and see the undefined 
> behavior, may make (possible surprising) optimizations on the based on 
> the assumed limited range of the shift count based on otherwise 
> undefined behavior.

While I do not question the legality of such "optimizations", I question their
usefulness.  Anything which can be accomplished with such optimization could
be accomplished more easily, efficiently, and safely by having the Standard
define some macros, e.g.

   __STDC_ASSUMING(x < 32) statement;

which would entitle the compiler to assume *while generating code for the
following statement* that at the start of the statement x would be less than
32, or

    __STC_CHECKED_ASSUME(x < 32);

which would allow, but not require, a compiler to raise a non-returnable
implementation-defined signal any time it could determine that that code
would be reached with x less than 32 (the directive would not allow the
compiler to do anything other than raise the signal).

Note that adding such directives to the Standard would not require that any
compilers do anything they don't already do, safe for adding a new header file
which defines the macros to yield either nothing or compiler intrinsics.

> the  a << (b & 0x1F) option should be simple on any reasonable platform, 
> adding only an instruction or two to the sequence. Note also that this 
> is only needed in the case of a program that overshifts and can accept 
> this results (the likely result on most systems for at least slight 
> overshifts if you ignored the UB).

A problem with the mod-shift behavior is that it wouldn't allow compilers for
the ARM to guarantee that when y is 32..127, x<<y will yield 0, and x>>y will
yield 0 if x is positive or -1 if x is negative, behavior which can frequently
be useful in graphics programming [curiously, the ARM compiler only guarantees
the behavior for 0..127, though the ARM chips I've used guarantee it based upon
the lower 8 bits of the shift value].

> Since was are assuming a 16x16->32 multiply (and a 16 bit int) the 
> 'extra' work is doing a 32 bit compare instead of 16 bit, which again is 
> pretty small. Again you are using the

In 8086 code, if a compiler recognized the 16x16->32 paradigm the code wouldn't
be horrible, but if the supposed purpose of requiring the cast to long is to
enable "optimization", requiring the programmer to write code that's less
efficient would seem contrary to that goal.  Further, if the code is not
intended to handle long values consistently, promoting to long for certain
calculations purely to avoid hyper-modern optimizations would tend to obscure
that fact.

> The undefined behavior is allowed to call launch_nuclear_missiles(), and 
> the as-if rule allows the order of execution to be largely re-arranged, 
> so we have no temporal anomaly. (Since we have no volatile objects in 
> the program, the only things that are "observable" are the getch(), the 
> printf()s and the return from main, which need to happen in the 
> specified order. Nothing using the value of ch is allowed to be moved 
> before the getch() call, but other than that, the sequencing is not 
> specified, as long as the rearrangement doesn't change defined behavior.

Is it stated clearly and unambiguously that behavior would be defined if
getch() exits via SIGINT or other such means?  I've not gotten consistent
responses on that issue, since the C Standard itself does not recognize the
possibility of getch() doing anything other than returning a value, and
compilers like gcc would frequently be used for platforms which don't support
any signals.

> Yes, bypassing undefined behavior can be hard. Generally, making the 
> routine a separately compiled function is enough to keep the UB from 
> propagating out, as what the compiler can see, it can't use against you. 
> There also is normally an implementation specific way to limit the 
> optimizations to avoid this issue.

Using a separately-compiled routine would certainly work if it was compiled
with options for deterministic overflow behavior, and would likely work anyway,
but that won't yield code nearly as what could have been yielded if there were
standards for loosely-defined behaviors.

> It is obvious that we will need to use some knowledge of the 
> implementation to meet your requirement, as there are (or at least were) 
> systems where this sort of undefined behavior did drastic things (like 
> abending your program).

In many cases, my biggest concern is with situations where a program receives
invalid input, raising a signal would be which couldn't return but could
setjmp() to recovery code would be a useful thing to do, and even abending the
program would be more acceptable than allowing a supplier of malicious imput
the ability to run arbitrary code, which is the behavior compiler writers seem
to favor.

> Of course, to meet your requirement f not violating causality, you need 
> to add stuff to the code to force your idea of causality.

What would you think of the idea of standardized macros, such that given:

__TCSB_REQUIRE(__STDC_ANY_INT_OVERFLOW, 
    __STDC_STDC_PARTIALLY_INTERMINATE_VALUE | 
    __STDC_NOTRET_TRAP_IN_SEQUENCE |
    __STDC_FOR_LOOP_EXIT)

a compiler would be required to either:

  (1) Guarantee that overflow involving any integer type would be required to
      either yield a partially indeterminate value, trap in implementation-
      defined fashion with all code prior to the overflow having been executed,
      and allowing for the possibility that a "for" loop may exit early (or
      skip execution altogether) in cases where overflow is going to occur,
      even before it actually happens, or

  (2) Regard the program as ill-formed

I believe it should be possible to achieve the required semantics in almost
any existing compiler merely by adding a suitable <tcsb.h> file, and such
macros would offer benefits for humans reading the code as well as machines.

[toc] | [prev] | [next] | [standalone]

#68187

On 8/23/15 10:04 PM, supercat@casperkitty.com wrote:
> On Sunday, August 23, 2015 at 5:46:53 PM UTC-5, Richard Damon wrote:
>> Thinking about it, WHAT "real-world" application is going to over shift
>> a value and work perfectly fine with either answer? (something beyond
>> resorting to a GIGO argument on user input).
>
> (1) Applications frequently need to guarantee that malicious input will have
>      no effect beyond yielding loosely-constrained garbage output.

So you constraint isn't the two results, but any normal "unspecified" 
behavior. Getting unknown results propagating through makes it much 
harder to verify that things are going to be sane. Much better to CHECK 
your values and make sure they are valid.

> (2) The normal way to write a "rotate left" function for rotate values 0-31
>      used to be "(dat << n) | (dat >> (32-n))".  That expression will work the
>      same regardless of whether "dat >> 32" yields dat or zero, and it's likely
>      that if a compiler can optimize anything to a "rotate left" instruction it
>      will optimize that.  Is anything gained by requiring programmers to use a
>      longer and ickier form?
>
using (0x1F&-n) or (0x1F^n) instead of (32-n) is fully standards 
conforming, and no longer or really ickier.

> (3) Many functions sometimes pay attention to certain arguments and sometimes
>      ignore them.  If the cases which would result in a value being shifted
>      by an excessive amount are also cases where its value will be ignored,
>      but no other special handling would be needed at the point of the shift,
>      letting the shift happen may be more efficient than adding code to prevent
>      it.
>
>> Also, I will point out that I can't imagine any compiler creating code
>> for the shift function that is other than naive expectation of the
>> machine shift code. Where the issue is that code CALLING the shift
>> function, if the compiler is able to look inside and see the undefined
>> behavior, may make (possible surprising) optimizations on the based on
>> the assumed limited range of the shift count based on otherwise
>> undefined behavior.
>
> While I do not question the legality of such "optimizations", I question their
> usefulness.  Anything which can be accomplished with such optimization could
> be accomplished more easily, efficiently, and safely by having the Standard
> define some macros, e.g.
>
>     __STDC_ASSUMING(x < 32) statement;
>
> which would entitle the compiler to assume *while generating code for the
> following statement* that at the start of the statement x would be less than
> 32, or
>
>      __STC_CHECKED_ASSUME(x < 32);
>
> which would allow, but not require, a compiler to raise a non-returnable
> implementation-defined signal any time it could determine that that code
> would be reached with x less than 32 (the directive would not allow the
> compiler to do anything other than raise the signal).
>
> Note that adding such directives to the Standard would not require that any
> compilers do anything they don't already do, safe for adding a new header file
> which defines the macros to yield either nothing or compiler intrinsics.
>
>> the  a << (b & 0x1F) option should be simple on any reasonable platform,
>> adding only an instruction or two to the sequence. Note also that this
>> is only needed in the case of a program that overshifts and can accept
>> this results (the likely result on most systems for at least slight
>> overshifts if you ignored the UB).
>
> A problem with the mod-shift behavior is that it wouldn't allow compilers for
> the ARM to guarantee that when y is 32..127, x<<y will yield 0, and x>>y will
> yield 0 if x is positive or -1 if x is negative, behavior which can frequently
> be useful in graphics programming [curiously, the ARM compiler only guarantees
> the behavior for 0..127, though the ARM chips I've used guarantee it based upon
> the lower 8 bits of the shift value].

You're changing your spec now! If you want ARM behavior on the ARM, then 
use the option on the compiler to not use aggressive optimization on UB. 
(i.e. use something implementation defined to get implementation 
dependent behavior). Since other processor won't get you the 0, to 
assume the standard will define it that way is bad.

>
>> Since was are assuming a 16x16->32 multiply (and a 16 bit int) the
>> 'extra' work is doing a 32 bit compare instead of 16 bit, which again is
>> pretty small. Again you are using the
>
> In 8086 code, if a compiler recognized the 16x16->32 paradigm the code wouldn't
> be horrible, but if the supposed purpose of requiring the cast to long is to
> enable "optimization", requiring the programmer to write code that's less
> efficient would seem contrary to that goal.  Further, if the code is not
> intended to handle long values consistently, promoting to long for certain
> calculations purely to avoid hyper-modern optimizations would tend to obscure
> that fact.

The purpose of the cast is to DISABLE an 'optimization' based on 
overflow. Note, in this case the UB optimization is likely fairly 
limited it ability as it was primarily the use of a constant to make it 
clear that overflow occurred. Having code that doesn't care about 
getting the 'right' answer, but is worried about a simple instruction 
seems off to me.
>
>> The undefined behavior is allowed to call launch_nuclear_missiles(), and
>> the as-if rule allows the order of execution to be largely re-arranged,
>> so we have no temporal anomaly. (Since we have no volatile objects in
>> the program, the only things that are "observable" are the getch(), the
>> printf()s and the return from main, which need to happen in the
>> specified order. Nothing using the value of ch is allowed to be moved
>> before the getch() call, but other than that, the sequencing is not
>> specified, as long as the rearrangement doesn't change defined behavior.
>
> Is it stated clearly and unambiguously that behavior would be defined if
> getch() exits via SIGINT or other such means?  I've not gotten consistent
> responses on that issue, since the C Standard itself does not recognize the
> possibility of getch() doing anything other than returning a value, and
> compilers like gcc would frequently be used for platforms which don't support
> any signals.

I am not certain, but it looks like the standard defines that SIGINT 
would go to the defined signal handler, or some default action (SIG_IGN 
or SIG_DEF, as implementation defined). The likely default action (I 
would expect it to be implementation defined, but I am not certain) 
would be to call abort(), _Exit(), or quick_exit(), so a SIGINT says 
getch() doesn't return.
>
>> Yes, bypassing undefined behavior can be hard. Generally, making the
>> routine a separately compiled function is enough to keep the UB from
>> propagating out, as what the compiler can see, it can't use against you.
>> There also is normally an implementation specific way to limit the
>> optimizations to avoid this issue.
>
> Using a separately-compiled routine would certainly work if it was compiled
> with options for deterministic overflow behavior, and would likely work anyway,
> but that won't yield code nearly as what could have been yielded if there were
> standards for loosely-defined behaviors.

The idea of a separately compiled routine is that in that small routine, 
the implementation will generate the obvious instruction sequence, 
yielding for you the natural machine dependent behavior for the 
undefined behavior. Since the calling routine can't see into the routine 
to see the cases that create undefined behavior, the calling routine 
can't do UB based optimizations. Of course, this IS dependent on the 
natural machine's undefined behavior in this case is acceptable.
>
>> It is obvious that we will need to use some knowledge of the
>> implementation to meet your requirement, as there are (or at least were)
>> systems where this sort of undefined behavior did drastic things (like
>> abending your program).
>
> In many cases, my biggest concern is with situations where a program receives
> invalid input, raising a signal would be which couldn't return but could
> setjmp() to recovery code would be a useful thing to do, and even abending the
> program would be more acceptable than allowing a supplier of malicious imput
> the ability to run arbitrary code, which is the behavior compiler writers seem
> to favor.

The normal 'hyper-optimization' isn't arbitrary code, but other code 
making the assumption that values that cause UB don't need to be 
considered (and thus go down possibly unpredicted paths, possibly 
leading to more UB). OF course, the proper method is to detect the bad 
values up front. Note also, the cases that get optimized are almost 
always simple values that make obvious UB (things like NULL)
>
>> Of course, to meet your requirement f not violating causality, you need
>> to add stuff to the code to force your idea of causality.
>
> What would you think of the idea of standardized macros, such that given:
>
> __TCSB_REQUIRE(__STDC_ANY_INT_OVERFLOW,
>      __STDC_STDC_PARTIALLY_INTERMINATE_VALUE |
>      __STDC_NOTRET_TRAP_IN_SEQUENCE |
>      __STDC_FOR_LOOP_EXIT)
>
> a compiler would be required to either:
>
>    (1) Guarantee that overflow involving any integer type would be required to
>        either yield a partially indeterminate value, trap in implementation-
>        defined fashion with all code prior to the overflow having been executed,
>        and allowing for the possibility that a "for" loop may exit early (or
>        skip execution altogether) in cases where overflow is going to occur,
>        even before it actually happens, or
>
>    (2) Regard the program as ill-formed
>
> I believe it should be possible to achieve the required semantics in almost
> any existing compiler merely by adding a suitable <tcsb.h> file, and such
> macros would offer benefits for humans reading the code as well as machines.
>

A macro like that would be very different than anything in the standard. 
More likely is macros set for how the compiler is currently set (so the 
program can generate an error if incompatible). Another possibility 
would be a pragma indicating desired behavior classes, with a diagnostic 
generated if the compiler doesn't support that option.

[toc] | [prev] | [next] | [standalone]

#68194

On Sunday, August 23, 2015 at 10:40:44 PM UTC-5, Richard Damon wrote:
> On 8/23/15 10:04 PM, supercat@casperkitty.com wrote:
> > (1) Applications frequently need to guarantee that malicious input will have
> >      no effect beyond yielding loosely-constrained garbage output.
> 
> So you constraint isn't the two results, but any normal "unspecified" 
> behavior. Getting unknown results propagating through makes it much 
> harder to verify that things are going to be sane. Much better to CHECK 
> your values and make sure they are valid.

That depends what's going to be done with the results, and what could usefully
be done if the values are invalid.  If code is supposed to render an encoded
graphic image into a series of 4x8-bit RGBA pixels, and the recipient of
those pixels would be prepared to receive any possible combination of RGBA
values therein, having invalid input yield invalid output may be more efficient
than trying to catch all possible overflows.

> using (0x1F&-n) or (0x1F^n) instead of (32-n) is fully standards 
> conforming, and no longer or really ickier.

It would need to be "dat >> (31-n) >> 1", which on many compilers would
require an extra shift.

> The purpose of the cast is to DISABLE an 'optimization' based on 
> overflow. Note, in this case the UB optimization is likely fairly 
> limited it ability as it was primarily the use of a constant to make it 
> clear that overflow occurred. Having code that doesn't care about 
> getting the 'right' answer, but is worried about a simple instruction 
> seems off to me.

The effect of the cast is to disable all optimizations based on overflow, even
in cases where the programmer would be happy with a range of optimizing
behaviors.  If the purpose of aggressive flow-based optimization is to make
code more efficient, forcing programmers to specify casting behaviors which are
more rigid than what they actually need would be counterproductive.

> I am not certain, but it looks like the standard defines that SIGINT 
> would go to the defined signal handler, or some default action (SIG_IGN 
> or SIG_DEF, as implementation defined). The likely default action (I 
> would expect it to be implementation defined, but I am not certain) 
> would be to call abort(), _Exit(), or quick_exit(), so a SIGINT says 
> getch() doesn't return.

The Gnu Compiler Collection is designed for use on a variety of runtime
libraries, some of which would support SIGINT and some of which would have
no concept of such a thing, and the compiler has no way of knowing whether
any particular library would ever raise SIGINT.  Would anything in the C
Standard require that a compiler which can't be certain that the implementation
of "getch()" which is being used will always return must presume that it may
fail to do so?

> > Using a separately-compiled routine would certainly work if it was compiled
> > with options for deterministic overflow behavior, and would likely work anyway,
> > but that won't yield code nearly as what could have been yielded if there were
> > standards for loosely-defined behaviors.
> 
> The idea of a separately compiled routine is that in that small routine, 
> the implementation will generate the obvious instruction sequence, 
> yielding for you the natural machine dependent behavior for the 
> undefined behavior. Since the calling routine can't see into the routine 
> to see the cases that create undefined behavior, the calling routine 
> can't do UB based optimizations. Of course, this IS dependent on the 
> natural machine's undefined behavior in this case is acceptable.

Unfortunately, if the goal was to achieve good performance, splitting little
bits of code into separate units that can't be in-lined is counter-productive.
Further, given trends in whole-program optimization, hoping that a compiler
won't see across module boundaries is no longer a safe solution.

> > In many cases, my biggest concern is with situations where a program receives
> > invalid input, raising a signal would be which couldn't return but could
> > setjmp() to recovery code would be a useful thing to do, and even abending the
> > program would be more acceptable than allowing a supplier of malicious imput
> > the ability to run arbitrary code, which is the behavior compiler writers seem
> > to favor.
> 
> The normal 'hyper-optimization' isn't arbitrary code, but other code 
> making the assumption that values that cause UB don't need to be 
> considered (and thus go down possibly unpredicted paths, possibly 
> leading to more UB). OF course, the proper method is to detect the bad 
> values up front. Note also, the cases that get optimized are almost 
> always simple values that make obvious UB (things like NULL)

A number of security vulnerabilities have already popped up in production
systems because an optimizing compiler bypassed security checks which would
have caught problems.  Given something like:

   int blah(int mode, int x, int y)
   {
     if (x > 1000000)
     {
       if (mode)
         return do_something(x,y);
     }
     else
       return x*y;
   }

a hyper-modern compiler could optimize a call to blah(m, v, 10000); as

     if (v > 1000000)
       do_something(x,10000);

Provided that the function was also invoked sometimes with smaller values of
y, there would be no basis for a compiler to issue a diagnostic for the above
code (since the omitted test for "mode" would sometimes be used), but omitting
the test for "mode" could very easily allow totally unintended behavior which
could easily lead to arbitrary code execution.

> > What would you think of the idea of standardized macros, such that given:
> >
> > __TCSB_REQUIRE(__STDC_ANY_INT_OVERFLOW,
> >      __STDC_STDC_PARTIALLY_INTERMINATE_VALUE |
> >      __STDC_NOTRET_TRAP_IN_SEQUENCE |
> >      __STDC_FOR_LOOP_EXIT)
> >
> > a compiler would be required to either:
> >
> >    (1) Guarantee that overflow involving any integer type would be required to
> >        either yield a partially indeterminate value, trap in implementation-
> >        defined fashion with all code prior to the overflow having been executed,
> >        and allowing for the possibility that a "for" loop may exit early (or
> >        skip execution altogether) in cases where overflow is going to occur,
> >        even before it actually happens, or
> >
> >    (2) Regard the program as ill-formed
> >
> > I believe it should be possible to achieve the required semantics in almost
> > any existing compiler merely by adding a suitable <tcsb.h> file, and such
> > macros would offer benefits for humans reading the code as well as machines.
> >
> 
> A macro like that would be very different than anything in the standard. 
> More likely is macros set for how the compiler is currently set (so the 
> program can generate an error if incompatible). Another possibility 
> would be a pragma indicating desired behavior classes, with a diagnostic 
> generated if the compiler doesn't support that option.

From the point of view of the Standard, any program containing any #pragma
directives that aren't blocked via #ifdef or #if automatically invokes
Undefined Behavior, so that's no good.

The reason I favor the syntax I suggested is that it should be possible for
existing compilers even back to C89 to implement __TCSB_REQUIRE etc. as macros
(possibly rather ugly ones), but newer compilers could implement them as
intrinsics, and could automatically adjust their behavior to match requirements,
and would also make it easy to define a category of standard-conformance for
programs.  If the Standard didn't define a standard macro for __TCSB_REQUIRE
than for purposes of brevity a lot of programmers would end up defining their
own, but they'd all be different, making it much harder for source-code analysis
tools to determine program requirements.  Using standardized macros would make
it much easier, five years down the road, to answer questions like "What
fraction of programs require X but don't require Y", thus allowing compiler
writers to identify what combinations of optimizations should most usefully be
supported.

[toc] | [prev] | [next] | [standalone]

#68202

On Monday, August 24, 2015 at 6:48:20 AM UTC+1, supe...@casperkitty.com wrote:
>
> That depends what's going to be done with the results, and what could 
> usefully be done if the values are invalid.  If code is supposed to 
> render an encoded graphic image into a series of 4x8-bit RGBA pixels, 
> and the recipient of those pixels would be prepared to receive any
> possible combination of RGBA values therein, having invalid input yield
> invalid output may be more efficient than trying to catch all possible
> overflows.
> 
In reality, valid input is going to cause overflows, and you need to
litter such code with clamp() macros. Often the processor will 
do saturating adds for you, but there's no access to it from standard
C.

[toc] | [prev] | [next] | [standalone]

#67779

On 08/18/2015 07:19 PM, supercat@casperkitty.com wrote:
> On Saturday, December 20, 2014 at 12:36:33 PM UTC-6, James Kuyper wrote:

It's been eight months since I posted that message, you sure took a long
time to respond.

I had to search for my original message to find out what the context of
my comments was, my news server doesn't keep old messages that long.

Many people have described C as a portable assembley language, and
someone took that description too literally. He expected some C code to
be translated into machine language using a particular set of
instructions. Under circumstances where the behavior of the C code was
undefined, he expected the actual behavior to be that which would have
resulted from using that particular set of instructions. I pointed out
that C is NOT a high-level assembler. An assembler allows you to specify
what instructions should be generated, C only allows you to specify the
resulting behavior. As a result, the compiler is free to generate a
different set of instructions than the one he expected, so long as it
had the same behavior when the behavior was well-defined. The fact that
it generates different behavior than he expected when the behavior is
undefined doesn't violate any applicable requirements. In that context
(specifically, considering a shift by too many bits), I wrote:

>> It might seem perverse to produce any other result - until you consider
>> optimizations. A shift expression could be optimized completely out of
>> the generated code, or it could be combined with another expression, and
>> the combination might be replaced by a different set of instructions
>> that is better for some reason. As long as the alternative instructions
>> have behavior that matches the standard's requirements, when it imposes
>> some, it doesn't matter what the alternative code does when the behavior
>> is undefined.
> 
> A problem with that thinking is that it precludes the possibility of optimizing code based on a programmer's willingness to accept range of behaviors.  Consider the following requirement and a method written in C to meet it:

I find your whole discussion quite murky. I think that the key thing
that is missing is the alternative way of thinking that you're comparing
this to. I see no alternative way that is consistent with the actual
words of the standard that would avoid the issues you raise. If you have
thought of such a way, you should describe it.
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#67912

On 2015-08-18, supercat@casperkitty.com <supercat@casperkitty.com> wrote:
> A major key to facilitating behavior-based optimization in usable
> programs is that it should be possible to write code whose behavior is
> sufficiently constrained to meet programmer requirements, but
>  loosely-enough constrained to allow a compiler some flexibility.
> Consider the following requirements/function:
>
>     /* Requirement 1: If the arithmetical values of a*b and c*d are
>                       both representable as int, return 1 if a*b > c*d
>                       and 0 otherwise. */
>     int mulcomp(int a, int b, int c, int d)
>     {
>       return a*b > c*d;
>     }
>
> Nice and simple, easy to read, and easy to optimize on a wide range of platforms.  Now add one more requirement:
>
>     /* Requirement 2: Do not negate the laws of time and causality, even if
>                       a*b or c*d is outside the range of int */

It is possible to compute a*b > c*d without computing the products a*b and c*d.
First, there are trivial cases where the result of the comparison only
depends on the signs of a,b,c,d, for instance, if a,b,c are positive but d is
negative, a*b > c*d evaluates to some_positive_value > some_negative_value which
is trivially true.
If no trivial cases apply, it is possible to re-arrange the expression such that
a,b,c,d are all positive and a>=b and c>=d, so that
a*b > c*d can be rewritten (taking quotients and remainders) to an
expression that tests the sign of (a/d - c/b) * b*d + (b * a%d - d * c%b), where
the first term, (a/d - c/b) * b*d, is a multiple of b*d, and the second term,
(b * a%d - d * c%b) has a magnitude less than b*d.
That means that if a/d == b/c, the first term equals zero and the result only
depends on the sign of b * a%d - d * c%b (which can be computed recursively),
and if a/d != b/c the second term can be neglected and the result only depends
on a/d - c/b.
See below is for a sketch of the algorithm:

#include <stdlib.h>
#include <assert.h>

static void swap(int *x, int *y)
{
  int const t = *x; *x = *y; *y = t;
}

int mulcomp(int a, int b, int c, int d)
/* returns a*b > c*d without computing the products */
{
  if ((a==0 || b==0) && (c==0 || d==0)) return 0;
  if ((a==0 || b==0)) return (c>0) != (d>0);
  if ((c==0 || d==0)) return (a>0) == (b>0);
  assert(a!=0 && b!=0 && c!=0 && d!=0);
  if ((a>0) == (b>0) && (c>0) != (d>0)) return 1;
  if ((a>0) != (b>0) && (c>0) == (d>0)) return 0;
  assert(((a>0) == (b>0)) == ((c>0) == (d>0)));
  if ((a>0) != (b>0))
  {
    assert((c>0) != (d>0));
    swap(&a, &c); swap(&b, &d);
  }
  a = abs(a); c = abs(c); b = abs(b); d = abs(d);
  assert(0<a && 0<c && 0<b && 0<d);
  if (a<b) swap(&a, &b);
  if (c<d) swap(&c, &d);
  assert(0 < b && b <= a && 0 < d && d <= c);
  div_t const ad = div(a, d), cb = div(c, b);
  return ad.quot == cb.quot ? mulcomp(b, ad.rem, d, cb.rem) : ad.quot > cb.quot;
}

[toc] | [prev] | [next] | [standalone]

#67916

On Thursday, August 20, 2015 at 4:46:40 PM UTC-5, Ike Naar wrote:
> int mulcomp(int a, int b, int c, int d)
> /* returns a*b > c*d without computing the products */

I wonder if any compiler could optimize that to yield code anywhere near as
efficient as a*b > c*d?  Bear in mind that the stated requirements did not
require that the comparison yield an arithmetically-correct result in case of
overflow--arbitrarily returning 0 or 1 would be acceptable.

My main point was "strictly-compliant C" is a virtually useless language where
absurdly-complicated code is required to do things that should be very simple.
Given "return a*b > c*d;" how long should it take for a reasonable programmer
to confirm that it yields the correct result in all cases where a*b and c*d
are both representable as int?  If you added logic to handle the cases where
your code presently invokes Undefined Behavior (and on many platforms would
die with an assertion failure), how long should it take for a reasonable
programmer to confirm its correctness?

[toc] | [prev] | [next] | [standalone]

#67923

Ike Naar wrote:
> It is possible to compute a*b > c*d without computing the products
> a*b and c*d.

> 
> #include <stdlib.h>
> #include <assert.h>
> 
> static void swap(int *x, int *y)
> {
>   int const t = *x; *x = *y; *y = t;
> }
> 
> int mulcomp(int a, int b, int c, int d)
> /* returns a*b > c*d without computing the products */
> {
>   if ((a==0 || b==0) && (c==0 || d==0)) return 0;
>   if ((a==0 || b==0)) return (c>0) != (d>0);
>   if ((c==0 || d==0)) return (a>0) == (b>0);
>   assert(a!=0 && b!=0 && c!=0 && d!=0);
>   if ((a>0) == (b>0) && (c>0) != (d>0)) return 1;
>   if ((a>0) != (b>0) && (c>0) == (d>0)) return 0;
>   assert(((a>0) == (b>0)) == ((c>0) == (d>0)));
>   if ((a>0) != (b>0))
>   {
>     assert((c>0) != (d>0));
>     swap(&a, &c); swap(&b, &d);
>   }
>   a = abs(a); c = abs(c); b = abs(b); d = abs(d);
>   assert(0<a && 0<c && 0<b && 0<d);
>   if (a<b) swap(&a, &b);
>   if (c<d) swap(&c, &d);
>   assert(0 < b && b <= a && 0 < d && d <= c);
>   div_t const ad = div(a, d), cb = div(c, b);
>   return ad.quot == cb.quot ? mulcomp(b, ad.rem, d, cb.rem) : ad.quot > cb.quot;
> }

I think you just proved his point.

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

Back to top | Article view | comp.lang.c

csiph-web